A *pair* (sometimes called a *dotted pair*) is a data structure
with two fields called the *car* and *cdr* fields (for
historical reasons). Pairs are created by the procedure `cons`

.
The car and cdr fields are accessed by the procedures `car`

and
`cdr`

. The car and cdr fields are assigned by the procedures
`set-car!`

and `set-cdr!`

.

Pairs are used primarily to represent *lists*. A list can be
defined recursively as either the empty list or a pair whose cdr is
a list. More precisely, the set of lists is defined as the smallest set
`X` such that

- The empty list is in
`X`. - If
`list`is in`X`, then any pair whose cdr field contains`list`is also in`X`.

The objects in the car fields of successive pairs of a list are the
*elements* of the list. For example, a two-element list is a pair
whose car is the first element and whose cdr is a pair whose car is the
second element and whose cdr is the empty list. The *length* of a
list is the number of elements, which is the same as the number of
pairs. The *empty list* is a special object of its own type (it is
not a pair); it has no elements and its length is zero.^{5}

The most general notation (external representation) for Scheme pairs is
the “dotted” notation `(`

where `c1` . `c2`)`c1` is
the value of the car field and `c2` is the value of the cdr field.
For example, `(4 . 5)`

is a pair whose car is `4`

and whose
cdr is `5`

. Note that `(4 . 5)`

is the external
representation of a pair, not an expression that evaluates to a pair.

A more streamlined notation can be used for lists: the elements of the
list are simply enclosed in parentheses and separated by spaces. The
empty list is written `()`

. For example, the following are
equivalent notations for a list of symbols:

(a b c d e) (a . (b . (c . (d . (e . ())))))

Whether a given pair is a list depends upon what is stored in the cdr
field. When the `set-cdr!`

procedure is used, an object can be a
list one moment and not the next:

(define x (list 'a 'b 'c)) (define y x) y ⇒ (a b c) (list? y) ⇒ #t (set-cdr! x 4) ⇒ unspecified x ⇒ (a . 4) (eqv? x y) ⇒ #t y ⇒ (a . 4) (list? y) ⇒ #f (set-cdr! x x) ⇒ unspecified (list? y) ⇒ #f

A chain of pairs that doesn’t end in the empty list is called an
*improper list*. Note that an improper list is not a list. The
list and dotted notations can be combined to represent improper lists,
as the following equivalent notations show:

(a b c . d) (a . (b . (c . d)))

Within literal expressions and representations of objects read by the
`read`

procedure, the forms `'`

,
`datum````

, `datum``,`

, and `datum``,@`

denote two-element lists whose first elements are the symbols
`datum``quote`

, `quasiquote`

, `unquote`

, and
`unquote-splicing`

, respectively. The second element in each case
is `datum`. This convention is supported so that arbitrary Scheme
programs may be represented as lists. Among other things, this permits
the use of the `read`

procedure to parse Scheme programs.

• Pairs | ||

• Construction of Lists | ||

• Selecting List Components | ||

• Cutting and Pasting Lists | ||

• Filtering Lists | ||

• Searching Lists | ||

• Mapping of Lists | ||

• Folding of Lists | ||

• Miscellaneous List Operations |

The above definitions imply that all lists have finite length and are terminated by the empty list.