LISP - Accessing Element of Sequence

Modern Lisp: Accessing Sequence Elements

In Common Lisp, a sequence is an abstract data type representing an ordered collection. The most common concrete sequence types are lists, vectors, and strings. Lisp provides a rich set of functions to access their elements, but it’s crucial to choose the right function based on the data structure to ensure both correctness and performance.

Accessing Elements of a List

Lists in Lisp are implemented as linked lists. Access is therefore most efficient at the head of the list.

first (car) and rest (cdr)

first returns the first element, and rest returns the remainder of the list. While the traditional names car and cdr are still valid, the modern names first and rest are more descriptive and often preferred for clarity.

(let ((my-list '(a b c)))
  (format t "First element: ~a~%" (first my-list)) ; -> A
  (format t "Rest of list: ~s~%" (rest my-list)))   ; -> (B C)

second, third, …, tenth

For convenience, Lisp provides accessor functions for the first ten elements of a list.

(let ((my-list '(a b c d e)))
  (format t "Third element: ~a~%" (third my-list))) ; -> C

nth - Access by Index (With a Warning)

nth returns the element at a specific zero-based index. Warning: Because lists are linked lists, nth must traverse the list from the beginning. This is an O(n) operation and can be very slow for long lists.

;; Get the element at index 2 (the third element)
(format t "Element at index 2: ~a~%" (nth 2 '(a b c d e))) ; -> C

Accessing Elements of Vectors and Strings

Vectors and strings are array-like structures that provide fast, O(1) random access to their elements.

elt - The General-Purpose Sequence Accessor

elt (element) is a polymorphic function that works on any sequence type. It takes a sequence and a zero-based index and returns the element at that position. This is the recommended modern approach for general sequence access.

(let ((my-vector #(10 20 30))
      (my-string "Lisp"))
  ;; Accessing a vector element
  (format t "Vector element at index 1: ~a~%" (elt my-vector 1)) ; -> 20

  ;; Accessing a string character
  (format t "String char at index 2: ~a~%" (elt my-string 2)))   ; -> #\s

aref - The Array-Specific Accessor

aref (array reference) is specialized for arrays (including vectors and strings). In modern Lisp implementations, its performance is typically identical to elt for vectors and strings. Its main use is when you need to be explicit that you are working with an array, or when working with multi-dimensional arrays, where it’s the required accessor.

(let ((my-vector #(10 20 30)))
  (format t "Vector element with aref: ~a~%" (aref my-vector 1))) ; -> 20

Choosing the Right Accessor: A Summary

Data Structure	Access Pattern	Recommended Function(s)	Performance
List	First Element	first (or car)	O(1)
List	Nth Element	nth (use with caution)	O(n)
Vector	Nth Element	elt (or aref)	O(1)
String	Nth Character	elt (or aref)	O(1)

Best Practices and Error Handling

• Data Structure Choice: The performance difference between nth and elt highlights a key design principle in Lisp. If you need frequent, fast, random access by index, use a vector, not a list.
• Bounds Checking: Accessing an index that is out of bounds for a sequence will signal an error. Always ensure your index is valid before attempting to access an element, for example by checking against (length sequence).
• Clarity is Key: Prefer first, rest, second, etc. over car, cdr, cadr in modern code unless you are in a context where the c...r tradition is very strong (e.g., deep in compiler-like code).
• Prefer elt for Generality: When writing functions that should operate on any kind of sequence, use elt for element access to make your code more general and reusable.