Go to the first, previous, next, last section, table of contents.


Lists

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

The most general notation (external representation) for Scheme 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 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, ,datum, and ,@datum denote two-element lists whose first elements 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 Scheme programs may be represented as lists. Among other things, this permits the use of the read procedure to parse Scheme programs.

Pairs

This section describes the simple operations that are available for constructing and manipulating arbitrary graphs constructed from pairs.

procedure: pair? object
Returns #t if object is a pair; otherwise returns #f.

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

procedure: cons obj1 obj2
Returns 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 previously 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
Returns the contents of the car field of pair. Note that it is 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--> Illegal datum

procedure: cdr pair
Returns the contents of the cdr field of pair. Note that it is an error to take the cdr of the empty list.

(cdr '((a) b c d))                      =>  (b c d)
(cdr '(1 . 2))                          =>  2
(cdr '())                               error--> Illegal datum

procedure: set-car! pair object
Stores object in the car field of pair. The value returned by set-car! is unspecified.

(define (f) (list 'not-a-constant-list))
(define (g) '(constant-list))
(set-car! (f) 3)                        =>  unspecified
(set-car! (g) 3)                        error--> Illegal datum

procedure: set-cdr! pair object
Stores object in the cdr field of pair. The value returned by set-cdr! is unspecified.

procedure: caar pair
procedure: cadr pair
procedure: cdar pair
procedure: cddr pair
procedure: caaar pair
procedure: caadr pair
procedure: cadar pair
procedure: caddr pair
procedure: cdaar pair
procedure: cdadr pair
procedure: cddar pair
procedure: cdddr pair
procedure: caaaar pair
procedure: caaadr pair
procedure: caadar pair
procedure: caaddr pair
procedure: cadaar pair
procedure: cadadr pair
procedure: caddar pair
procedure: cadddr pair
procedure: cdaaar pair
procedure: cdaadr pair
procedure: cdadar pair
procedure: cdaddr pair
procedure: cddaar pair
procedure: cddadr pair
procedure: cdddar pair
procedure: cddddr pair
These procedures are compositions of car and cdr; for example, caddr could be defined by

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

procedure+: general-car-cdr object path
This procedure is a generalization of car and cdr. Path encodes a particular sequence of car and cdr operations, which general-car-cdr executes on object. Path is an exact non-negative integer that encodes the operations in a bitwise fashion: a zero bit represents a cdr operation, and a one bit represents a car. The bits are executed LSB to MSB, and the most significant one bit, rather than being interpreted as an operation, signals the end of the sequence.(9)

For example, the following are equivalent:

(general-car-cdr object #b1011)
(cdr (car (car object)))

Here is a partial table of path/operation equivalents:

#b10    cdr
#b11    car
#b100   cddr
#b101   cdar
#b110   cadr
#b111   caar
#b1000  cdddr

procedure+: tree-copy tree
This copies an arbitrary tree constructed from pairs, copying both the car and cdr elements of every pair. This could have been defined by

(define (tree-copy tree)
  (let loop ((tree tree))
    (if (pair? tree)
        (cons (loop (car tree)) (loop (cdr tree)))
        tree)))

Construction of Lists

procedure: list object ...
Returns a list of its arguments.

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

These expressions are equivalent:

(list obj1 obj2 ... objN)
(cons obj1 (cons obj2 ... (cons objN '()) ...))

procedure+: make-list k [element]
This procedure returns a newly allocated list of length k, whose elements are all element. If element is not supplied, it defaults to the empty list.

procedure+: cons* object object ...
cons* is similar to list, except that cons* conses together the last two arguments rather than consing the last argument with the empty list. If the last argument is not a list the result is an improper list. If the last argument is a list, the result is a list consisting of the initial arguments and all of the items in the final argument. If there is only one argument, the result is the argument.

(cons* 'a 'b 'c)                        =>  (a b . c)
(cons* 'a 'b '(c d))                    =>  (a b c d)
(cons* 'a)                              =>  a

These expressions are equivalent:

(cons* obj1 obj2 ... objN-1 objN)
(cons obj1 (cons obj2 ... (cons objN-1 objN) ...))

procedure+: list-copy list
Returns a newly allocated copy of list. This copies each of the pairs comprising list. This could have been defined by

(define (list-copy list)
  (if (null? list)
      '()
      (cons (car list)
            (list-copy (cdr list)))))

procedure: vector->list vector
procedure+: subvector->list vector start end
vector->list returns a newly allocated list of the elements of vector. subvector->list returns a newly allocated list of the elements of the given subvector. The inverse of vector->list is list->vector.

(vector->list '#(dah dah didah))        =>  (dah dah didah)

procedure: string->list string
procedure: substring->list string start end
string->list returns a newly allocated list of the character elements of string.
substring->list returns a newly allocated list of the character elements of the given substring. The inverse of string->list is list->string.

(string->list "abcd")                   =>  (#\a #\b #\c #\d)
(substring->list "abcdef" 1 3)          =>  (#\b #\c)

Selecting List Components

procedure+: list? object
Returns #t if object is a list, otherwise returns #f. By definition, all lists have finite length and are terminated by the empty list. This procedure returns an answer even for circular structures.

Any object satisfying this predicate will also satisfy exactly one of pair? or null?.

(list? '(a b c))                        =>  #t
(list? '())                             =>  #t
(list? '(a . b))                        =>  #f
(let ((x (list 'a)))
  (set-cdr! x x)
  (list? x))                            =>  #f

procedure: length list
Returns the length of list.

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

procedure: null? object
Returns #t if object is the empty list; otherwise returns #f (but see section True and False).

(null? '(a . b))                        =>  #f
(null? '(a b c))                        =>  #f
(null? '())                             =>  #t

procedure: list-ref list k
Returns the kth element of list, using zero-origin indexing. The valid indexes of a list are the exact non-negative integers less than the length of the list. The first element of a list has index 0, the second has index 1, and so on.

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

(list-ref list k) is equivalent to (car (list-tail list k)).

procedure+: first list
procedure+: second list
procedure+: third list
procedure+: fourth list
procedure+: fifth list
procedure+: sixth list
procedure+: seventh list
procedure+: eighth list
procedure+: ninth list
procedure+: tenth list
Returns the specified element of list. It is an error if list is not long enough to contain the specified element (for example, if the argument to seventh is a list that contains only six elements).

Cutting and Pasting Lists

procedure+: sublist list start end
Start and end must be exact integers satisfying

0 <= start <= end <= (length list)

sublist returns a newly allocated list formed from the elements of list beginning at index start (inclusive) and ending at end (exclusive).

procedure+: list-head list k
Returns a newly allocated list consisting of the first k elements of list. K must not be greater than the length of list.

We could have defined list-head this way:

(define (list-head list k)
  (sublist list 0 k))

procedure: list-tail list k
Returns the sublist of list obtained by omitting the first k elements. The result, if it is not the empty list, shares structure with list. K must not be greater than the length of list.

procedure: 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))
(append)                                =>  ()

The resulting list is always newly allocated, except that it shares structure with the last list argument. 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

procedure+: append! list ...
Returns a list that is the argument lists concatenated together. The arguments are changed rather than copied. (Compare this with append, which copies arguments rather than destroying them.) For example:

(define x '(a b c))
(define y '(d e f))
(define z '(g h))
(append! x y z)                         =>  (a b c d e f g h)
x                                       =>  (a b c d e f g h)
y                                       =>  (d e f g h)
z                                       =>  (g h)

Filtering Lists

procedure+: list-transform-positive list predicate
procedure+: list-transform-negative list predicate
These procedures return a newly allocated copy of list containing only the elements for which predicate is (respectively) true or false. Predicate must be a procedure of one argument.

(list-transform-positive '(1 2 3 4 5) odd?) => (1 3 5)
(list-transform-negative '(1 2 3 4 5) odd?) => (2 4)

procedure+: delq element list
procedure+: delv element list
procedure+: delete element list
Returns a newly allocated copy of list with all entries equal to element removed. delq uses eq? to compare element with the entries in list, delv uses eqv?, and delete uses equal?.

procedure+: delq! element list
procedure+: delv! element list
procedure+: delete! element list
Returns a list consisting of the top-level elements of list with all entries equal to element removed. These procedures are like delq, delv, and delete except that they destructively modify list. delq! uses eq? to compare element with the entries in list, delv! uses eqv?, and delete! uses equal?. Because the result may not be eq? to list, it is desirable to do something like (set! x (delete! x)).

(define x '(a b c b))
(delete 'b x)                           =>  (a c)
x                                       =>  (a b c b)

(define x '(a b c b))
(delete! 'b x)                          =>  (a c)
x                                       =>  (a c)
;; Returns correct result:
(delete! 'a x)                          =>  (c)

;; Didn't modify what x points to:
x                                       =>  (a c)

procedure+: delete-member-procedure deletor predicate
Returns a deletion procedure similar to delv or delete!. Deletor should be one of the procedures list-deletor or list-deletor!. Predicate must be an equivalence predicate. The returned procedure accepts exactly two arguments: first, an object to be deleted, and second, a list of objects from which it is to be deleted. If deletor is list-deletor, the procedure returns a newly allocated copy of the given list in which all entries equal to the given object have been removed. If deletor is list-deletor!, the procedure returns a list consisting of the top-level elements of the given list with all entries equal to the given object removed; the given list is destructively modified to produce the result. In either case predicate is used to compare the given object to the elements of the given list.

Here are some examples that demonstrate how delete-member-procedure could have been used to implement delv and delete!:

(define delv (delete-member-procedure list-deletor eqv?))
(define delete! (delete-member-procedure list-deletor! equal?))

procedure+: list-deletor predicate
procedure+: list-deletor! predicate
These procedures each return a procedure that deletes elements from lists. Predicate must be a procedure of one argument. The returned procedure accepts exactly one argument, which must be a proper list, and applies predicate to each of the elements of the argument, deleting those for which it is true.

The procedure returned by list-deletor deletes elements non-destructively, by returning a newly allocated copy of the argument with the appropriate elements removed. The procedure returned by list-deletor! performs a destructive deletion.

Searching Lists

procedure+: list-search-positive list predicate
procedure+: list-search-negative list predicate
Returns the first element in list for which predicate is (respectively) true or false; returns #f if it doesn't find such an element. (This means that if predicate is true (false) for #f, it may be impossible to distinguish a successful result from an unsuccessful one.) Predicate must be a procedure of one argument.

procedure: memq object list
procedure: memv object list
procedure: member object list
These procedures return the first pair of list whose car is object; the returned pair is always one from which list is composed. If object does not occur in list, #f (n.b.: not the empty list) is returned. memq uses eq? to compare object with the elements of list, while memv uses eqv? and member uses equal?.(10)

(memq 'a '(a b c))                      =>  (a b c)
(memq 'b '(a b c))                      =>  (b c)
(memq 'a '(b c d))                      =>  #f
(memq (list 'a) '(b (a) c))             =>  #f
(member (list 'a) '(b (a) c))           =>  ((a) c)
(memq 101 '(100 101 102))               =>  unspecified
(memv 101 '(100 101 102))               =>  (101 102)

procedure+: member-procedure predicate
Returns a procedure similar to memq, except that predicate, which must be an equivalence predicate, is used instead of eq?. This could be used to define memv as follows:

(define memv (member-procedure eqv?))

Mapping of Lists

procedure: map procedure list list ...
Procedure must be a procedure taking as many arguments as there are lists. If more than one list is given, then they must all be the same length. map applies procedure element-wise to the elements of the lists and returns a list of the results, in order from left to right. The dynamic order in which procedure is applied to the elements of the lists is unspecified; use for-each to sequence side effects.

(map cadr '((a b) (d e) (g h)))           =>  (b e h)
(map (lambda (n) (expt n n)) '(1 2 3 4))  =>  (1 4 27 256)
(map + '(1 2 3) '(4 5 6))                 =>  (5 7 9)
(let ((count 0))
  (map (lambda (ignored)
         (set! count (+ count 1))
         count)
       '(a b c)))                         =>  unspecified

procedure+: map* initial-value procedure list1 list2 ...
Similar to map, except that the resulting list is terminated by initial-value rather than the empty list. The following are equivalent:

(map procedure list list ...)
(map* '() procedure list list ...)

procedure+: append-map procedure list list ...
procedure+: append-map* initial-value procedure list list ...
Similar to map and map*, respectively, except that the results of applying procedure to the elements of lists are concatenated together by append rather than by cons. The following are equivalent, except that the former is more efficient:

(append-map procedure list list ...)
(apply append (map procedure list list ...))

procedure+: append-map! procedure list list ...
procedure+: append-map*! initial-value procedure list list ...
Similar to map and map*, respectively, except that the results of applying procedure to the elements of lists are concatenated together by append! rather than by cons. The following are equivalent, except that the former is more efficient:

(append-map! procedure list list ...)
(apply append! (map procedure list list ...))

procedure: for-each procedure list list ...
The arguments to for-each are like the arguments to map, but for-each calls procedure for its side effects rather than for its values. Unlike map, for-each is guaranteed to call procedure on the elements of the lists in order from the first element to the last, and the value returned by for-each is 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)

Reduction of Lists

procedure+: reduce procedure initial list
Combines all the elements of list using the binary operation procedure. For example, using + one can add up all the elements:

(reduce + 0 list-of-numbers)

The argument initial is used only if list is empty; in this case initial is the result of the call to reduce. If list has a single argument, it is returned. Otherwise, the arguments are reduced in a left-associative fashion. For example:

(reduce + 0 '(1 2 3 4))                 =>  10
(reduce + 0 '(1 2))                     =>  3
(reduce + 0 '(1))                       =>  1
(reduce + 0 '())                        =>  0
(reduce + 0 '(foo))                     =>  foo
(reduce list '() '(1 2 3 4))            =>  (((1 2) 3) 4)

procedure+: reduce-right procedure initial list
Like reduce except that it is right-associative.

(reduce-right list '() '(1 2 3 4))      =>  (1 (2 (3 4)))

procedure+: fold-right procedure initial list
Combines all of the elements of list using the binary operation procedure. Unlike reduce and reduce-right, initial is always used:

(fold-right + 0 '(1 2 3 4))             =>  10
(fold-right + 0 '(foo))                 error--> Illegal datum
(fold-right list '() '(1 2 3 4))        =>  (1 (2 (3 (4 ()))))

Fold-right has interesting properties because it establishes a homomorphism between (cons, ()) and (procedure, initial). It can be thought of as replacing the pairs in the spine of the list with procedure and replacing the () at the end with initial. Many of the classical list-processing procedures can be expressed in terms of fold-right, at least for the simple versions that take a fixed number of arguments:

(define (copy-list list)
  (fold-right cons '() list))

(define (append list1 list2)
  (fold-right cons list2 list1))

(define (map p list) 
  (fold-right (lambda (x r) (cons (p x) r)) '() list))

(define (reverse items)
  (fold-right (lambda (x r) (append r (list x))) '() items))

procedure+: fold-left procedure initial list
Combines all the elements of list using the binary operation procedure. Elements are combined starting with initial and then the elements of list from left to right. Whereas fold-right is recursive in nature, capturing the essence of cdr-ing down a list and then computing a result, fold-left is iterative in nature, combining the elements as the list is traversed.

(fold-left list '() '(1 2 3 4))         =>  ((((() 1) 2) 3) 4)

(define (length list)
  (fold-left (lambda (sum element) (+ sum 1)) 0 list))

(define (reverse items)
  (fold-left (lambda (x y) (cons y x)) () items))

procedure+: there-exists? list predicate
Predicate must be a procedure of one argument. Applies predicate to each element of list, in order from left to right. If predicate is true for any element of list, the value yielded by predicate is immediately returned as the value of there-exists?; predicate will not be applied to the remaining elements of list. If predicate returns #f for all of the elements of list, then #f is returned.

procedure+: for-all? list predicate
Predicate must be a procedure of one argument. Applies predicate to each element of list, in order from left to right. If predicate returns #f for any element of list, #f is immediately returned as the value of for-all?; predicate will not be applied to the remaining elements of list. If predicate is true for all of the elements of list, then #t is returned.

Miscellaneous List Operations

procedure+: circular-list object ...
procedure+: make-circular-list k [element]
These procedures are like list and make-list, respectively, except that the returned lists are circular. circular-list could have been defined like this:

(define (circular-list . objects)
  (append! objects objects))

procedure: reverse list
Returns a newly allocated list consisting of the top-level 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+: reverse! list
Returns a list consisting of the top-level elements of list in reverse order. reverse! is like reverse, except that it destructively modifies list. Because the result may not be eqv? to list, it is desirable to do something like (set! x (reverse! x)).

procedure+: last-pair list
Returns the last pair in list, which may be an improper list. last-pair could have been defined this way:

(define last-pair
  (lambda (x)
    (if (pair? (cdr x))
        (last-pair (cdr x))
        x)))

procedure+: except-last-pair list
procedure+: except-last-pair! list
These procedures remove the last pair from list. List may be an improper list, except that it must consist of at least one pair. except-last-pair returns a newly allocated copy of list that omits the last pair. except-last-pair! destructively removes the last pair from list and returns list. If the cdr of list is not a pair, the empty list is returned by either procedure.

procedure+: sort sequence procedure
Sequence must be either a list or a vector. Procedure must be a procedure of two arguments that defines a total ordering on the elements of sequence. In other words, if x and y are two distinct elements of sequence, then it must be the case that

(and (procedure x y)
     (procedure y x))
     =>  #f

If sequence is a list (vector), sort returns a newly allocated list (vector) whose elements are those of sequence, except that they are rearranged to be sorted in the order defined by procedure. So, for example, if the elements of sequence are numbers, and procedure is <, then the resulting elements are sorted in monotonically nondecreasing order. Likewise, if procedure is >, the resulting elements are sorted in monotonically nonincreasing order. To be precise, if x and y are any two adjacent elements in the result, where x precedes y, it is the case that

(procedure y x)
     =>  #f

See also the definition of sort!.


Go to the first, previous, next, last section, table of contents.