Next: Symbols Up: Standard procedures Previous: Booleans Index
Pairs and listsA 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 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 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 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? 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 can be represented as lists. That is, according to Scheme's grammar, every expression is also a datum. Among other things, this permits the read procedure to parse Scheme programs. See section 3.3.
(pair?
obj
)
procedure
The pair? predicate 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
(cons
obj1 obj2
)
procedure
Returns a newly allocated pair whose car is obj1 and whose
cdr is obj2. The pair is guaranteed to be
different(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)
(car
pair
)
procedure
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
(cdr
pair
)
procedure
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
(set-car!
pair obj
)
special form
Stores obj in the car field of pair.
(define (f) (list 'not-a-constant-list))
(set-car! (f) 3) ==> unspecified
(set-cdr!
pair obj
)
special form
Stores obj in the cdr field of pair.
(caar
pair
)
procedure
(cadr
pair
)
procedure
(cdar
pair
)
procedure
(cddr
pair
)
procedure
These procedures are compositions of car and cdr as follows:
(define (caar x) (car (car x)))
(define (cadr x) (car (cdr x)))
(define (cdar x) (cdr (car x)))
(define (cddr x) (cdr (cdr x)))
(caaar
pair
)
cxr library procedure
(caadr
pair
)
cxr library procedure
...
...
(cdddar
pair
)
cxr library procedure
(cddddr
pair
)
cxr library procedure
These twenty-four procedures are further compositions of
car and cdr on the same principles. For example, caddr
could be defined by
(define caddr (lambda (x) (car (cdr (cdr x))))).
Arbitrary compositions up to four deep are provided.
(null?
obj
)
procedure
Returns #t if obj is the empty list, otherwise returns #f.
(list?
obj
)
procedure
Returns #t if obj is a list. Otherwise, it returns #f. By
definition, all lists have finite length and are terminated by
the empty list.
(list? obj ) procedure
(list? '(a b c)) ==> #t
(list? '()) ==> #t
(list? '(a . b)) ==> #f
(let ((x (list 'a)))
(set-cdr! x x)
(list? x)) ==> #f
(make-list
k
)
procedure
(make-list
k fill
)
procedure
Returns a newly allocated list of k elements. If a second
argument is given, then each element is initialized to fill.
Otherwise the initial contents of each element is unspecified.
(make-list 2 3) ==> (3 3)
(list
obj ...
)
procedure
Returns a newly allocated list of its arguments.
(list 'a (+ 3 4) 'c) ==> (a 7 c)
(list) ==> ()
(length
list
)
procedure
Returns the length of list .
(length '(a b c)) ==> 3
(length '(a (b) (c d e))) ==> 3
(length '()) ==> 0
(append
list ...
)
procedure
The last argument, if there is one, can be of any type.
Returns a list consisting of the elements of the first list followed by the elements of the other list s. If there are no arguments, the empty list is returned. If there is exactly one argument, it is returned. Otherwise the resulting list is always newly allocated, except that it shares structure with the last argument. An improper list results if the last argument is not a proper list.
(append '(x) '(y)) ==> (x y)
(append '(a) '(b c d)) ==> (a b c d)
(append '(a (b)) '((c))) ==> (a (b) (c))
(append '(a b) '(c . d)) ==> (a b c . d)
(append '() 'a) ==> a
(reverse
list
)
procedure
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)
(list-tail
list k
)
procedure
It is an error if list has fewer than k elements.
Returns the sublist of list obtained by omitting the first k elements.
(list-ref
list k
)
procedure
It is an error if list has fewer than k elements.
Returns the kth element of list . (This is the same as the car of (list-tail list k).)
(list-ref '(a b c d) 2) ==> c
(list-ref '(a b c d)
(exact (round 1.8)))
==> c
(list-set!
list k obj
)
special form
It is an error if k is not a valid index of list.
The list-set! procedure stores obj in element k of list.
(let ((ls (list 'one 'two 'five!)))
(list-set! ls 2 'three)
ls)
==> (one two three)
(memq
obj list
)
procedure
(memv
obj list
)
procedure
(member
obj list
)
procedure
(member
obj list compare
)
procedure
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 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. The memq procedure uses eq? to compare
obj with the elements of list , while memv uses eqv? and
member uses compare, if given, and equal? otherwise.
(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)
(member "B"
'("a" "b" "c")
string-ci=?) ==> ("b" "c")
(memq 101 '(100 101 102)) ==> unspecified
(memv 101 '(100 101 102)) ==> (101 102)
(assq
obj alist
)
procedure
(assv
obj alist
)
procedure
(assoc
obj alist
)
procedure
(assoc
obj alist compare
)
procedure
It is an error if alist (for \association list") is not 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. The assq procedure uses eq? to compare obj with the car fields of the pairs in alist , while assv uses eqv? and assoc uses compare if given and equal? otherwise.
(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))
(assoc 2.0 '((1 1) (2 4) (3 9)) ==>
==> (2 4)
(assq 5 '((2 3) (5 7) (11 13)))
==> unspecified
(assv 5 '((2 3) (5 7) (11 13)))
==> (5 7)
Rationale: Although they are often used as predicates, memq, memv, member, assq, assv, and assoc do not have question marks in their names because they return potentially useful values rather than just #t or #f.
(list-copy
obj
)
procedure
Returns a newly allocated copy of the given obj if it is a
list. Only the pairs themselves are copied; the cars of the
result are the same (in the sense of eqv?) as the cars of list .
If obj is an improper list, so is the result, and the final cdrs
are the same in the sense of eqv?. An obj which is not a
list is returned unchanged. It is an error if obj is a circular
list.
(define a '(1 8 2 8))
(define b (list-copy a))
(set-car! b 3)
b ==> (3 8 2 8)
a ==> (1 8 2 8)
|