LISP - Sequences

Lisp - Working with Sequences

A sequence is a fundamental abstract data type in Common Lisp. It represents an ordered collection of elements. The two most common concrete types of sequences are lists and vectors. Most sequence functions work on both, making your code flexible and general.

1. Creating and Accessing Sequences

You can create sequences directly or with make-sequence. Accessing elements is done with the elt function.

;; A list is created with ' or (list ...)
(defvar my-list '(a b c d e))

;; A vector is created with #(...)
(defvar my-vector #(10 20 30 40 50))

;; Create a sequence programmatically
(defvar my-generated-vector (make-sequence 'vector 5 :initial-element 0))
;=> #(0 0 0 0 0)

;; Access the 3rd element (0-indexed) of the list
(format t "List element at index 2: ~a~%" (elt my-list 2)) ;=> C

;; Access the 4th element of the vector
(format t "Vector element at index 3: ~a~%" (elt my-vector 3)) ;=> 40

;; Get the length of a sequence
(format t "Length of my-list: ~d~%" (length my-list)) ;=> 5

2. Modifying Sequences: Destructive vs. Non-Destructive

A critical concept in Lisp is the distinction between functions that modify a sequence in-place (destructive) and those that return a new, modified sequence (non-destructive).

• Non-Destructive: Safer, but can be less efficient as they allocate new memory. Examples: remove, substitute, reverse.
• Destructive: More memory-efficient, but modify the original data. Often prefixed with n (e.g., nreverse) or named with verbs like delete or fill. Use with caution!

Example: Removing and Substituting Elements

(let ((data '(1 5 2 5 3 5)))
  ;; REMOVE (non-destructive) returns a new list
  (let ((new-data (remove 5 data)))
    (format t "Original data after REMOVE: ~a~%" data) ;=> (1 5 2 5 3 5)
    (format t "Result of REMOVE: ~a~%" new-data))       ;=> (1 2 3)
  (terpri)

  ;; DELETE (destructive) modifies the original list structure
  (let ((modifiable-data (list 1 5 2 5 3 5)))
    (delete 5 modifiable-data)
    (format t "Data after DELETE: ~a~%" modifiable-data)) ;=> (1 2 3) (or similar)
  (terpri)

  ;; SUBSTITUTE (non-destructive)
  (let ((substituted (substitute 99 5 data :count 1)))
    (format t "Result of SUBSTITUTE: ~a~%" substituted)) ;=> (1 99 2 5 3 5)
)

3. Higher-Order Functions: Mapping and Filtering

Lisp excels at using functions as data. You can apply functions across sequences to transform or filter them without writing explicit loops.

(defvar numbers '(1 2 3 4 5 6))

;; MAPCAR applies a function to each element of a list
(let ((squared (mapcar #'(lambda (x) (* x x)) numbers)))
  (format t "Squared numbers: ~a~%" squared)) ;=> (1 4 9 16 25 36)

;; REMOVE-IF-NOT (filter) keeps elements that satisfy a predicate
(let ((even-numbers (remove-if-not #'evenp numbers)))
  (format t "Even numbers: ~a~%" even-numbers)) ;=> (2 4 6)

;; COUNT-IF counts elements satisfying a predicate
(let ((odd-count (count-if #'oddp numbers)))
  (format t "Count of odd numbers: ~d~%" odd-count)) ;=> 3

;; REDUCE combines elements with a binary function
(let ((sum (reduce #'+ numbers)))
  (format t "Sum of numbers: ~d~%" sum)) ;=> 21

4. Sorting and Merging

The sort function modifies a sequence in-place, while merge combines two already-sorted sequences.

(let ((unsorted-data (list 9 1 8 2 7 3)))
  ;; SORT is destructive!
  (sort unsorted-data #'<)
  (format t "Sorted data: ~a~%" unsorted-data)) ;=> (1 2 3 7 8 9)

(let ((list1 '(1 5 10))
      (list2 '(2 4 12)))
  ;; MERGE is non-destructive
  (let ((merged (merge 'list list1 list2 #'<)))
    (format t "Merged list: ~a~%" merged))) ;=> (1 2 4 5 10 12)

5. Sequence Predicates

These functions test if elements of a sequence satisfy a condition. They are highly efficient as they stop as soon as the outcome is known (short-circuiting).

(defvar nums '(2 4 6 8))
(defvar mixed-nums '(1 2 3 4))

;; EVERY - Are all elements even?
(format t "All even in ~a? ~a~%" nums (every #'evenp nums)) ;=> T
(format t "All even in ~a? ~a~%" mixed-nums (every #'evenp mixed-nums)) ;=> NIL

;; SOME - Is at least one element odd?
(format t "Some odd in ~a? ~a~%" nums (some #'oddp nums)) ;=> NIL
(format t "Some odd in ~a? ~a~%" mixed-nums (some #'oddp mixed-nums)) ;=> T

Useful Keyword Arguments

Many sequence functions accept keyword arguments to customize their behavior:

Argument	Meaning	Default
:test	A two-argument function to compare elements (e.g., #'equal for nested lists).	#'eql
:key	A one-argument function to extract a value from an element before comparison.	#'identity
:start, :end	Operate on a subsequence from a start index up to (but not including) an end index.	0, nil
:from-end	If true, traverse the sequence from right to left.	nil
:count	Limit the number of elements affected (remove, substitute).	nil