LISP - Lists

Lisp Fundamentals: Lists and Cons Cells

Lists are the quintessential data structure in Lisp, so much so that the language’s name is an acronym for List Processing. While modern Common Lisp offers powerful alternatives like vectors and hash tables, a deep understanding of lists is fundamental to mastering the language.

The Building Block: The cons Cell

At the lowest level, lists are built from a simple structure called a cons cell. A cons cell is a pair of pointers, named car (Contents of the Address Register) and cdr (Contents of the Decrement Register)—historical names from the IBM 704 computer where Lisp was first implemented.

The cons function creates a new cons cell. It takes two arguments:

;; A cons cell where the CAR is 1 and the CDR is 2
;; This is printed as a "dotted pair"
(cons 1 2)   ; => (1 . 2)

;; Accessing the parts
(car (cons 1 2)) ; => 1
(cdr (cons 1 2)) ; => 2

A proper list is a chain of cons cells linked by their cdrs, where the final cdr is the special empty list value, nil.

;; A list with one element: (1)
(cons 1 nil)

;; A list with three elements: (1 2 3)
;; This is how it's structured internally:
(cons 1 (cons 2 (cons 3 nil)))

;; Diagram:
;;  [o|/]-- -> [o|/]-- -> [o|/]--> NIL
;;   |          |
;;   |          |
;;   v          v
;;   1          2

Creating Lists with list

While you can build lists by nesting cons calls, it’s cumbersome. The list function is the convenient way to create a list from a number of elements.

(list 1 2 3)         ; => (1 2 3)
(list 'a 'b 'c)      ; => (A B C)
(list 1 "hello" t)   ; => (1 "hello" T)

;; Lists can be nested
(list 'a (list 1 2) 'c) ; => (A (1 2) C)

Common List Manipulation Functions

Common Lisp provides a rich library of functions for working with lists. Here are some of the most essential ones:

Function	Description
car or first	Returns the first element of a list.
cdr or rest	Returns the list containing all but the first element.
cons	Adds a new element to the front of a list.
append	Merges two or more lists into a new list.
reverse	Returns a new list with elements in reverse order.
length	Returns the number of top-level elements in the list.
member	Checks if an element is in a list.
nth	Accesses the element at a specific index (zero-based).

Example in Action

(defparameter *my-list* '(a b c))

(first *my-list*)     ; => A
(rest *my-list*)      ; => (B C)

;; Add a new element to the front
(cons 'x *my-list*)   ; => (X A B C)
;; Note: *my-list* is unchanged! => (A B C)

(nth 1 *my-list*)     ; => B

(append *my-list* '(d e)) ; => (A B C D E)

Advanced Access: c...r and Destructuring

For nested lists, Lisp provides convenient shortcuts like cadr (short for (car (cdr list))), caddr, etc. These can be useful for simple, fixed structures.

(defparameter *nested-list* '(a (b c) d))

;; Get the second element: (B C)
(cadr *nested-list*)  ; equivalent to (second *nested-list*) or (nth 1 *nested-list*)

;; Get the first element of the second element: B
(caadr *nested-list*) ; equivalent to (first (second *nested-list*))

Modern Practice: For complex structures, using these shortcuts can become unreadable. Modern Lisp style often prefers the destructuring-bind macro, which lets you bind variables to parts of a list in a single, clear expression.

;; Using destructuring-bind is much clearer!
(destructuring-bind (first-item (second-item-a second-item-b) third-item)
    *nested-list*
  (format t "Items are: ~a, ~a, ~a, and ~a~%"
          first-item second-item-a second-item-b third-item))
;; Output: Items are: A, B, C, and D