4.8 Pairs and lists

A pair is a compound 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 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.

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

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 can 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.

Procedure: pair? obj

Return #t if obj is a pair, #f otherwise.

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

Procedure: cons obj1 obj2

Return a newly allocated pair whose car is obj1 and whose cdr is obj2. The pair is guaranteed to be different (in the sense of eqv?) from every existing object.

(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)

Procedure: car pair

Return the contents of the car field of pair.

(car '(a b c))          ⇒ a
(car '((a) b c d))      ⇒ (a)
(car '(1 . 2))          ⇒ 1
(car '())               ⇒ exception &assertion

Procedure: cdr pair

Return the contents of the cdr field of pair.

(cdr '((a) b c d))      ⇒ (b c d)
(cdr '(1 . 2))          ⇒ 2
(cdr '())               ⇒ exception &assertion

Procedure: caar pair

Procedure: cadr pair

Procedure: ...

Procedure: cdddar pair

Procedure: 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.

Procedure: null? obj

Return #t if obj is the empty list, #f otherwise.

Procedure: list? obj

Return #t if obj is a list, #f otherwise. By definition, all lists are chains of pairs that have finite length and are terminated by the empty list.

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

Procedure: list obj …

Return a newly allocated list of its arguments.

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

Procedure: length list

Return the length of list.

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

Procedure: append

Procedure: append list … obj

Return a possibly improper list consisting of the elements of the first list followed by the elements of the other lists, with obj as the cdr of the final pair. An improper list results if obj is not a list.

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

If append constructs a non–empty chain of pairs, it is always newly allocated. If no pairs are allocated, obj is returned.

R6RS mandates that this function requires at least the argument obj; it is illegal to call this function with no arguments. Despite this: The Scheme implementations supported by Nausicaa (Mosh, Petite Chez, Vicare, Ypsilon) allow calling this function with no arguments, in which case the return value is the empty string. The (nausicaa) language will ensure this behaviour. (Fri Jun 5, 2009)

Procedure: reverse list

Return a newly allocated 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)

Procedure: list-tail list k

list should be a list of size at least k. Return the subchain of pairs of list obtained by omitting the first k elements.

(list-tail '(a b c d) 2)        ⇒  (c d)

Implementation responsibilities: The implementation must check that list is a chain of pairs whose length is at least k. It should not check that it is a chain of pairs beyond this length.

Procedure: list-ref list k

list must be a list whose length is at least k + 1. The list-tail procedure returns the kth element of list.

(list-ref '(a b c d) 2)         ⇒ c

Implementation responsibilities: The implementation must check that list is a chain of pairs whose length is at least k + 1. It should not check that it is a list of pairs beyond this length.

Procedure: map proc list1 list2 …

The lists should all have the same length. proc should accept as many arguments as there are lists and return a single value. proc should not mutate any of the lists.

The map procedure applies proc element–wise to the elements of the lists and returns a list of the results, in order. proc is always called in the same dynamic environment as map itself. The order in which proc is applied to the elements of the lists is unspecified. If multiple returns occur from map, the values returned by earlier returns are not mutated.

(map cadr '((a b) (d e) (g h)))         ⇒  (b e h)

(map (lambda (n) (expt n n))
     '(1 2 3 4 5))                      ⇒  (1 4 27 256 3125)

(map + '(1 2 3) '(4 5 6))               ⇒  (5 7 9)

(let ((count 0))
  (map (lambda (ignored)
         (set! count (+ count 1))
         count)
       '(a b)))                         ⇒  (1 2) or (2 1)

Implementation responsibilities: The implementation should check that the lists all have the same length. The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.

Procedure: for-each proc list1 list2 …

The lists should all have the same length. proc should accept as many arguments as there are lists. proc should not mutate any of the lists.

The for-each procedure applies proc element–wise to the elements of the lists for its side effects, in order from the first elements to the last. proc is always called in the same dynamic environment as for-each itself. The return values of for-each are unspecified.

(let ((v (make-vector 5)))
  (for-each (lambda (i)
              (vector-set! v i (* i i)))
            '(0 1 2 3 4))
  v)
⇒  #(0 1 4 9 16)

(for-each (lambda (x) x) '(1 2 3 4))
⇒ unspecified

(for-each even? '())
⇒ unspecified

Implementation responsibilities: The implementation should check that the lists all have the same length. The implementation must check the restrictions on proc to the extent performed by applying it as described. An implementation may check whether proc is an appropriate argument before applying it.

NOTE Implementations of for-each may or may not tail–call proc on the last elements.