Go to the previous, next section.
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.
This section describes the simple operations that are available for constructing and manipulating arbitrary graphs constructed from pairs.
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
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)
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
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.
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
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)))
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) ...))
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)
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
Returns the length of list.
(length '(a b c)) => 3 (length '(a (b) (c d e))) => 3 (length '()) => 0
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
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))
.
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).
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).
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))
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.
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
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)
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+: 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.
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.
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?))
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)
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 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.
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))
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)
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))
.
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 list procedure
Procedure must be a procedure of two arguments that defines a total ordering on the elements of list. In other words, if x and y are two distinct elements of list, then it must be the case that
(and (procedure x y) (procedure y x)) => #f
sort
returns a newly allocated list whose elements are the
elements of list, except that the elements are rearranged so that
they are sorted in the order defined by procedure. So, for
example, if the elements of list are numbers, and procedure
is <
, then the resulting list is sorted in monotonically
nondecreasing order. Likewise, if procedure is >
, the
resulting list is sorted in monotonically nonincreasing order. To be
precise, if x and y are any two adjacent elements in the
resulting list, where x precedes y, it is the case that
(procedure y x) => #f
Go to the previous, next section.