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.
#t if object is a pair; otherwise returns
#f.
(pair? '(a . b)) => #t (pair? '(a b c)) => #t (pair? '()) => #f (pair? '#(a b)) => #f
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)
car of the empty list.
(car '(a b c)) => a (car '((a) b c d)) => (a) (car '(1 . 2)) => 1 (car '()) error--> Illegal datum
cdr of the empty list.
(cdr '((a) b c d)) => (b c d) (cdr '(1 . 2)) => 2 (cdr '()) error--> Illegal datum
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
set-cdr! is unspecified.
car and cdr; for
example, caddr could be defined by
(define caddr (lambda (x) (car (cdr (cdr x)))))
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
(define (tree-copy tree)
(let loop ((tree tree))
(if (pair? tree)
(cons (loop (car tree)) (loop (cdr tree)))
tree)))
(list 'a (+ 3 4) 'c) => (a 7 c) (list) => ()
These expressions are equivalent:
(list obj1 obj2 ... objN) (cons obj1 (cons obj2 ... (cons objN '()) ...))
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) ...))
(define (list-copy list)
(if (null? list)
'()
(cons (car list)
(list-copy (cdr list)))))
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)
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)
#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
(length '(a b c)) => 3 (length '(a (b) (c d e))) => 3 (length '()) => 0
#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
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)).
seventh is a list that contains only
six elements).
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).
We could have defined list-head this way:
(define (list-head list k) (sublist list 0 k))
(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
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)
(list-transform-positive '(1 2 3 4 5) odd?) => (1 3 5) (list-transform-negative '(1 2 3 4 5) odd?) => (2 4)
delq uses eq? to compare
element with the entries in list, delv uses
eqv?, and delete uses equal?.
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)
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?))
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.
#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.
#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)
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?))
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
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 ...)
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 ...))
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 ...))
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)
+ 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)
reduce except that it is right-associative.
(reduce-right list '() '(1 2 3 4)) => (1 (2 (3 4)))
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))
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))
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.
#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.
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))
(reverse '(a b c)) => (c b a) (reverse '(a (b c) d (e (f)))) => ((e (f)) d (b c) a)
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)).
last-pair could have been defined this way:
(define last-pair
(lambda (x)
(if (pair? (cdr x))
(last-pair (cdr x))
x)))
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.
(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