5.5.2.1 List Structure

Each element in a list is given its own cons cell and stored in the car of that cell. The list is then constructed by having the cdr of a cell point to the cons cell containing the next element (and hence the entire rest of the list). The cdr of the cell containing the last element in the list is (). A list of zero elements is represented by ().

The read syntax of a list is an opening parenthesis, followed by the read syntax of zero or more space-separated objects, followed by a closing parenthesis. Alternatively, lists can be constructed ‘manually’ using dotted-pair notation.

All of the following examples result in the same list of five elements: the numbers from zero to four.

(0 1 2 3 4)

(0 . (1 . (2 . (3 . (4 . ())))))

(0 1 2 . (3 4))

An easy way to visualise lists and how they are constructed is to see each cons cell in the list as a separate box with pointers to its car and cdr,

+-----+-----+
|  o  |  o----> cdr
+--|--+-----+
   |
    --> car

Complex box-diagrams can now be drawn to represent lists. For example the following diagram represents the list (1 2 3 4).

+-----+-----+   +-----+-----+   +-----+-----+   +-----+-----+
|  o  |  o----> |  o  |  o----> |  o  |  o----> |  o  |  o----> ()
+--|--+-----+   +--|--+-----+   +--|--+-----+   +--|--+-----+
   |               |               |               |
    --> 1           --> 2           --> 3           --> 4

A more complex example, the list ((1 2) (foo bar)) can be drawn as,

+-----+-----+                          +-----+-----+
|  o  |  o---------------------------> |  o  |  o----> ()
+--|--+-----+                          +--|--+-----+
   |                                      |
+-----+-----+   +-----+-----+          +-----+-----+   +-----+-----+
|  o  |  o----> |  o  |  o----> ()     |  o  |  o----> |  o  |  o----> ()
+--|--+-----+   +--|--+-----+          +--|--+-----+   +--|--+-----+
   |               |                      |               |
    --> 1           --> 2                  --> foo         --> bar