|
|
In Scheme, lists actually are made up from cons cells. A cons cell is pair of pointers. For historical reasons, the object pointed to by the first pointer is called the CAR, while the object pointed to by the second pointer is called the CDR. The usual box-notation for diagramming cons cell is:
--- ---
| * | * |->CDR
--- ---
|
\ /
CAR
Each pointer can point to an atom, another cons cell, or a null value (also called the empty list). A proper list is one in which every CDR is another cons cell except the last, which points to the empty list. for example, the proper list (a (b c) d) would be
--- --- --- --- --- ---
| * | * |-> | * | * | -> | * | * | -> null
--- --- --- --- --- ---
| | |
\ / | \ /
a | d
|
\ /
--- --- --- ---
| * | * | -> | * | * | -> null
--- --- --- ---
| |
\ / \ /
b c
The pairs can be represented explicitly in the list by means of what is called dotted-pair notation. For example,
> '(a . ((b . (c . ())) . (d . ()))) (a (b c) d)
A list in which the CDR element is an atom is called an improper list; for example, (a . b) represents the improper list
--- ---
| * | * |->b
--- ---
|
\ /
a