Next: Symbols, Previous: Booleans, Up: Other data types [Contents][Index]

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
‘`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.

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

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 `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) ==>unspecifiedx ==> (a . 4) (eqv? x y) ==> #t y ==> (a . 4) (list? y) ==> #f (set-cdr! 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 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.
That is, according to Scheme’s grammar, every
<expression> is also a <datum> (see section see External representation).
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:
**set-car!***pair obj* -
Stores

`obj`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*

- procedure:
**set-cdr!***pair obj* -
Stores

`obj`in the cdr field of`pair`. The value returned by ‘`set-cdr!`’ 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 twenty-eight 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))) (set-cdr! 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`list`s.`(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:
**list-tail***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. ‘`List-tail`’ could be defined by`(define list-tail (lambda (x k) (if (zero? k) x (list-tail (cdr x) (- k 1)))))`

- library procedure:
**list-ref***list*`k` -
Returns the

`k`th element of`list`. (This is the same as the car of`(list-tail`.) It is an error if`list``k`)`list`has fewer than`k`elements.`(list-ref '(a b c d) 2) ==> c (list-ref '(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 non-empty lists returned by`(list-tail`for`list``k`)`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`.

Next: Symbols, Previous: Booleans, Up: Other data types [Contents][Index]