Writing GNU Emacs Extensions

Chapter 6. Lists

In this chapter:

• The Simple View of Lists

• List Details

• Recursive List Functions

• Iterative List Functions

• Other Useful List Functions

• Destructive List Operations

• Circular Lists?!

So far, we've seen lists in a few contexts, but we haven't really explored how they work and why they're useful. Since lists are central to Lisp, this chapter provides a thorough look at this data structure.

The Simple View of Lists

As we've already seen, a list in Lisp is a sequence of zero or more Lisp expressions enclosed in parentheses. Lists may be nested; that is, the enclosed subexpressions may include one or more lists. Here are a few examples:

(a b c)        ;list of three symbols
(7 "foo")      ;list of number and string
((4.12 31178)) ;list of one element: a sublist of two numbers

The empty list () is synonymous with the symbol nil.

The functions car and cdr ^[23] are used to access parts of a list: car yields the first element in a list, and cdr yields the remainder of the list (everything but the first element).

(car '(a b c)) ⇒ a
(cdr '(a b c)) ⇒ (b c)
(car (cdr '(a b c))) ⇒ b

(Recall that quoting an expression—even a complete list—means to use that expression literally. So '(a b c) means the list containing a, b, and c, not the result of calling function a on arguments b and c.)

The cdr of a one-element list is nil:

(cdr '(x)) ⇒ nil

The car and cdr of the empty list are both nil:

(car '()) ⇒ nil
(cdr '()) ⇒ nil

Note that this is also true of the list containing nil:

(car '(nil)) ⇒ nil
(cdr '(nil)) ⇒ nil

This ...