Common Lisp/Basic topics/Lists

This module is far from finished. Improvements are welcome.

Lists in common lisp are built up from pairs called cons cells. Each cell has two parts, historically named car (for the first part) and cdr (for the remainder).

(car . cdr)

Lists are implemented with cons cells by having the cdr of the first cell point to another cons cell.

The empty list is also known as nil, it's written representation is either the literal nil or the empty list: ().

You can create a list by using cons to construct a new cons cell with a left and right hand part:

  (cons 'a '())                     ⇒ (A)
  (cons 'a '(b))                    ⇒ (A B)
  (cons 'a (cons 'b (cons 'c nil))) ⇒ (A B C)

Keep in mind that it is possible to create a cons cell which is not a list:

  (cons 'a 'b) ⇒ (A . B)

This is called a dotted list. To be a proper list, the final cdr in the chain of cons cells must point to the empty list (nil). You can also create a list with the function list:

  (list 'a 'b 'c)   ⇒ (A B C)

which is equivalent to:

  (cons 'a (cons 'b (cons 'c '()))) ⇒ (A B C)
  (cons 'a (cons 'b (cons 'c nil))) ⇒ (A B C)
  (cons 'a '(b c))                  ⇒ (A B C)
  '(a b c)                          ⇒ (A B C)

You can access the members of a list with the functions car (or first) and cdr (or rest):

  (setf list '(a b c))
  (car list)    ⇒ a
  (first list)  ⇒ a

  (cdr list)    ⇒ (b c)
  (rest list)   ⇒ (b c)

Common Lisp also defines the functions second, third and fourth (on up to tenth). Note that second is not the same as cdr or rest. cdr and rest both return the remaining list after the first element, while second returns the second item in the list:

  (rest list)   ⇒ (b c)
  (second list) ⇒ b
  (third list)  ⇒ c
  (fourth list) ⇒ nil

Lists are sequences, so functions that operate on sequences also operate on lists:

  (subseq list 0 1)  ⇒ (a)
  (subseq list 0 2)  ⇒ (a b)

The function nth also allows you to retrieve selected items from a list:

  (nth 0 list)  ⇒ a

Note that the first item in a list is the 0th. Common Lisp also has several forms (functions and macros) for operating on the contents of lists. mapcar can be used to process each element of a list one at a time to build up a new list:

  (defun add2 (n)
    (+ 2 n))
  (mapcar #'add2 '(1 2 3))  ⇒ (3 4 5)

In that example, we were mapping over a single list so we used a unary function (a function of one argument). The #' is a special way to pass a function as an argument into a function. We will talk more about it in the next chapter. It is also possible to map over more than one list - the function must then take the same number of arguments as there are lists:

  (mapcar #'+ '(1 2 3) '(4 5 6)) ⇒ (5 7 9)