[ << ]  [ < ]  [ Up ]  [ > ]  [ >> ]  [Top]  [Contents]  [Index]  [ ? ] 
6.3.2 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’. The car and cdr fields are assigned by the procedures ‘setcar!’ and ‘setcdr!’.
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 twoelement 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.
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,
(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 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. When the setcdr!
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 (setcdr! x 4) ⇒ unspecified x ⇒ (a . 4) (eqv? x y) ⇒ #t y ⇒ (a . 4) (list? y) ⇒ #f (setcdr! x x) ⇒ unspecified (list? x) ⇒ #f
Within literal expressions and representations of objects read by the
read
procedure, the forms ’<datum>,
‘<datum>, ,<datum>, and
,@<datum> denote twoelement lists whose first elements are
the symbols quote
, quasiquote
, unquote
, and
unquotesplicing
, respectively. The second element in each case
is <datum>. This convention is supported so that arbitrary Scheme
programs may be represented as lists.
That is, according to Scheme’s grammar, every
<expression> is also a <datum> (see section External representations).
Among other things, this permits the use of the ‘read’ procedure to
parse Scheme programs. See section External representations.
 procedure: pair? obj

‘Pair?’ returns #t if obj is a pair, and 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 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
 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
 procedure: setcar! pair obj

Stores obj in the car field of pair. The value returned by ‘setcar!’ is unspecified.
(define (f) (list 'notaconstantlist)) (define (g) '(constantlist)) (setcar! (f) 3) ⇒ unspecified (setcar! (g) 3) ⇒ error
 procedure: setcdr! pair obj

Stores obj in the cdr field of pair. The value returned by ‘setcdr!’ is unspecified.
 library procedure: caar pair
 library procedure: cadr pair
 …: …
 library procedure: cdddar pair
 library 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 twentyeight of these procedures in all.
 library procedure: list? obj

Returns #t if obj is a list, 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 (let ((x (list 'a))) (setcdr! x x) (list? x)) ⇒ #f
 library procedure: list obj …,
Returns a newly allocated list of its arguments.
(list 'a (+ 3 4) 'c) ⇒ (a 7 c) (list) ⇒ ()
 library procedure: length list

Returns the length of list.
(length '(a b c)) ⇒ 3 (length '(a (b) (c d e))) ⇒ 3 (length '()) ⇒ 0
 library 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))
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
 library procedure: reverse list

Returns 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)
 library procedure: listtail list k

Returns the sublist of list obtained by omitting the first k elements. It is an error if list has fewer than k elements. ‘Listtail’ could be defined by
(define listtail (lambda (x k) (if (zero? k) x (listtail (cdr x) ( k 1)))))
 library procedure: listref list k

Returns the kth element of list. (This is the same as the car of (listtail list k).) It is an error if list has fewer than k elements.
(listref '(a b c d) 2) ⇒ c (listref '(a b c d) (inexact>exact (round 1.8))) ⇒ c
 library procedure: memq obj list
 library procedure: memv obj list
 library procedure: member obj list

These procedures return the first sublist of list whose car is obj, where the sublists of list are the nonempty lists returned by (listtail 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. ‘Memq’ uses ‘eq?’ to compare obj with the elements of list, while ‘memv’ uses ‘eqv?’ and ‘member’ uses ‘equal?’.
(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)
 library procedure: assq obj alist
 library procedure: assv obj alist
 library procedure: assoc obj alist

Alist (for “association list”) must be a list of pairs. These procedures find the first pair in alist whose car field is obj, and returns that pair. If no pair in alist has obj as its car, then #f (not the empty list) is returned. ‘Assq’ uses ‘eq?’ to compare obj with the car fields of the pairs in alist, while ‘assv’ uses ‘eqv?’ and ‘assoc’ uses ‘equal?’.
(define e '((a 1) (b 2) (c 3))) (assq 'a e) ⇒ (a 1) (assq 'b e) ⇒ (b 2) (assq 'd e) ⇒ #f (assq (list 'a) '(((a)) ((b)) ((c)))) ⇒ #f (assoc (list 'a) '(((a)) ((b)) ((c)))) ⇒ ((a)) (assq 5 '((2 3) (5 7) (11 13))) ⇒ unspecified (assv 5 '((2 3) (5 7) (11 13))) ⇒ (5 7)
Rationale: Although they are ordinarily used as predicates, ‘memq’, ‘memv’, ‘member’, ‘assq’, ‘assv’, and ‘assoc’ do not have question marks in their names because they return useful values rather than just #t or #f.
[ << ]  [ < ]  [ Up ]  [ > ]  [ >> ]  [Top]  [Contents]  [Index]  [ ? ] 
This document was generated on October 23, 2011 using texi2html 5.0.