8.5.3 Pairs and Lists

A pair (sometimes called a dotted pair) is a record 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. Pairs are used primarily to represent lists. A list may 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.

NOTE 13

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

[71] list = (datum*) | (datum+ . datum) | abbreviation

The most general notation (external representation) for pairs is the dotted notation (c1 . c2) where 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 may 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,

(a b c d e)

and

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

are equivalent notations for a list of symbols.

A chain of pairs not ending in the empty list is called an improper list. Note that an improper list is not a list. The list and dotted notations may be combined to represent improper lists:

(a b c . d)

is equivalent to

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

Whether a given pair is a list depends upon what is stored in the cdr field.

[72] abbreviation = abbrev-prefix datum

[73] abbrev-prefix = ' | &grave. | , | ,

Within literal expressions, the forms 'datum, &grave.datum, ,datum, and ,datum denote the two-element list whose first element are the symbols quote, quasiquote, unquote, and unquote-splicing, respectively. The second element in each case is datum. This convention is supported so that arbitrary expressions and portions of the specification may be represented as lists. That is, according to the DSSSL expression language grammar, every expression is also a datum, and a transformation-language-body is a sequence of datums.

8.5.3.1 Pair Type Predicate

(pair? obj)

Returns #t if obj is a pair, and otherwise returns #f.

(pair? '(a . b))          #t
(pair? '(a b c))          #t
(pair? '())               #f

8.5.3.2 Pair Construction Procedure

(cons obj1 obj2)

Returns a pair whose car is obj1 and whose cdr is obj2.

(cons 'a '())             (a)
(cons '(a) '(b c d))      ((a) b c d)
(cons "a" '(b c))         ("a" b c)
(cons 'a 3)               (a . 3)
(cons '(a b) 'c)          ((a b) . c)

8.5.3.3 car Procedure

(car pair)

Returns the contents of the car field of pair. Note that it shall be an error to take the car of the empty list.

(car '(a b c))            a
(car '((a) b c d))        (a)
(car '(1 . 2))            1
(car '())                 error

8.5.3.4 cdr Procedure

(cdr pair)

Returns the contents of the cdr field of pair. Note that it shall be an error to take the cdr of the empty list.

(cdr '((a) b c d))        (b c d)
(cdr '(1 . 2))            2
(cdr '())                 error

8.5.3.5 cr Procedures

(caar pair)

(cadr pair)

(cdar pair)

(cddr pair)

(caaar pair)

(caadr pair)

(cadar pair)

(caddr pair)

(cdaar pair)

(cdadr pair)

(cddar pair)

(cdddr pair)

(caaaar pair)

(caaadr pair)

(caadar pair)

(caaddr pair)

(cadaar pair)

(cadadr pair)

(caddar pair)

(cadddr pair)

(cdaaar pair)

(cdaadr pair)

(cdadar pair)

(cdaddr pair)

(cddaar pair)

(cddadr pair)

(cdddar pair)

(cddddr pair)

These procedures are compositions of car and cdr, where for example caddr could be defined by

(define caddr (lambda (x) (car (cdr (cdr x))))).

Arbitrary compositions, up to four deep, are provided. There are twenty-eight of these procedures in all.

8.5.3.6 Empty List Type Predicate

(null? obj)

Returns #t if obj is the empty list, and otherwise returns #f.

8.5.3.7 List Type Predicate

(list? obj)

Returns #t if obj is a list, and otherwise returns #f. By definition, all lists have finite length and are terminated by the empty list.

(list? '(a b c))       #t
(list? '())            #t
(list? '(a . b))       #f

8.5.3.8 List Construction

(list obj )

Returns a list of its arguments.

(list 'a (+ 3 4) 'c) (a 7 c)
(list) ()

8.5.3.9 List Length

(length list)

Returns the length of list.

(length '(a b c))                 3
(length '(a (b) (c d e)))         3
(length '())                      0

8.5.3.10 Lists Appendance

(append list )

Returns a list consisting of the elements of the first list followed by the elements of the other lists.

(append '(x) '(y))                (x y)
(append '(a) '(b c d))            (a b c d)
(append '(a (b)) '((c)))          (a (b) (c))

The last argument may actually be any object; an improper list results if the last argument is not a proper list.

(append '(a b) '(c . d)) (a b c . d)
(append '() 'a) a

8.5.3.11 List Reversal

(reverse list)

Returns a list consisting of the elements of list in reverse order.

(reverse '(a b c)) (c b a)
(reverse '(a (b c) d (e (f)))) ((e (f)) d (b c) a)

8.5.3.12 Sublist Extraction

(list-tail list k)

Returns the sublist of list obtained by omitting the first k elements. List-tail could be defined by

(define list-tail
  (lambda (x k)
    (if (zero? k)
        x
        (list-tail (cdr x) (- k 1)))))

8.5.3.13 List Access

(list-ref list k)

Returns the kth element of list. (This is the same as the car of (list-tail list k).)

(list-ref '(a b c d) 2) c
(list-ref '(a b c d)
(inexact->exact (round 1.8))) c

8.5.3.14 List Membership

(member obj list)

Returns the first sublist of list whose car is equal? to obj, where the sublists of list are the non-empty lists returned by (list-tail list k) for k less than the length of list. If obj does not occur in list, then #f (not the empty list) is returned.

(member 'a '(a b c))                (a b c)
(member 'b '(a b c))                (b c)
(member 'a '(b c d))                #f

8.5.3.15 Association Lists

(assoc obj alist)

alist (for association list) shall be a list of pairs. This procedure finds the first pair in alist whose car field is equal? to obj and returns that pair. If no pair in alist has obj as its car, then #f (not the empty list) is returned.

(define e '((a 1) (b 2) (c 3)))
(assoc 'a e)       (a 1)
(assoc 'b e)       (b 2)
(assoc 'd e)       #f

NOTE 14

Although they are ordinarily used as predicates, member and assoc do not have question marks in their names because they return useful values rather than just #t or #f.