6.3. Lists and Pairs
6.3. Lists and Pairs
The pair, or cons cell, is the most fundamental of Scheme's structured object types. The most common use for pairs is to build lists, which are ordered sequences of pairs linked one to the next by the cdr field. The elements of the list occupy the car fields of the pairs. The cdr of the last pair in a proper list is the empty list, (); the cdr of the last pair in an improper list can be anything other than ().
Pairs may be used to construct binary trees. Each pair in the tree structure is an internal node of the binary tree; its car and cdr are the children of the node.
Proper lists are printed as sequences of objects separated by whitespace (that is, blanks, tabs, and newlines) and enclosed in parentheses. Brackets ( [ ] ) may also be used in some Scheme systems. For example, (1 2 3) and (a (nested list)) are proper lists. The empty list is written as ().
Improper lists and trees require a slightly more complex syntax. A single pair is written as two objects separated by whitespace and a dot, e.g., (a . b). This is referred to as dotted-pair notation. Improper lists and trees are also written in dotted-pair notation; the dot appears wherever necessary, e.g., (1 2 3 . 4) or ((1 . 2) . 3). Proper lists may be written in dotted-pair notation as well. For example, (1 2 3) may be written as (1 . (2 . (3 . ()))).
Unless otherwise stated, it is an error to pass an improper list to a procedure requiring a list argument.
It is possible to create a circular list or a cyclic graph by destructively altering the car or cdr field of a pair, using set-car! or set-cdr!. Some of the procedures listed in this section may loop indefinitely when handed a cyclic structure.
| (cons obj1 obj2) | procedure |
| returns: a new pair whose car and cdr are obj1 and obj2 | |
cons is the pair constructor procedure. obj1 becomes the car and obj2 becomes the cdr of the new pair.
(cons 'a '()) ⇒ (a) (cons 'a '(b c)) ⇒ (a b c) (cons 3 4) ⇒ (3 . 4)
| (car pair) | procedure |
| returns: the car of pair | |
It is an error to ask for the car of the empty list.
(car '(a)) ⇒ a (car '(a b c)) ⇒ a (car (cons 3 4)) ⇒ 3
| (cdr pair) | procedure |
| returns: the cdr of pair | |
It is an error to ask for the cdr of the empty list.
(cdr '(a)) ⇒ () (cdr '(a b c)) ⇒ (b c) (cdr (cons 3 4)) ⇒ 4
| (set-car! pair obj ) | procedure |
| returns: unspecified | |
set-car! changes the car of pair to obj.
(let ((x '(a b c))) (set-car! x 1) x) ⇒ (1 b c)
| (set-cdr! pair obj ) | procedure |
| returns: unspecified | |
set-cdr! changes the cdr of pair to obj.
(let ((x '(a b c))) (set-cdr! x 1) x) ⇒ (a . 1)
| (caar pair) | procedure |
| (cadr pair) | procedure |
| ⋮ | |
| (cddddr pair) | procedure |
| returns: the caar, cadr, …, or cddddr of pair | |
These procedures are defined as the composition of up to four cars and cdrs. The a's and d's between the c and r represent the application of car or cdr in order from right to left. For example, the procedure cadr applied to a pair yields the car of the cdr of the pair and is equivalent to (lambda (x) (car (cdr x))).
(caar '((a))) ⇒ a (cadr '(a b c)) ⇒ b (cdddr '(a b c d)) ⇒ (d) (cadadr '(a (b c))) ⇒ c
| (list obj ...) | procedure |
| returns: a list of obj ... | |
list is equivalent to (lambda x x).
(list) ⇒ () (list 1 2 3) ⇒ (1 2 3) (list 3 2 1) ⇒ (3 2 1)
| (list? obj ) | procedure |
| returns: #t if obj is a proper list, #f otherwise | |
list? must return #f for all improper lists, including cyclic lists. A definition of list? is shown on page 64.
(list? '()) ⇒ #t (list? '(a b c)) ⇒ #t (list? 'a) ⇒ #f (list? '(3 . 4)) ⇒ #f (list? 3) ⇒ #f (let ((x (list 'a 'b 'c))) (set-cdr! (cddr x) x) (list? x)) ⇒ #f
| (length list) | procedure |
| returns: the number of elements in list | |
length may be defined as follows.
(define length (lambda (ls) (let loop ((ls ls) (n 0)) (if (null? ls) n (loop (cdr ls) (+ n 1)))))) (length '()) ⇒ 0 (length '(a b c)) ⇒ 3
| (list-ref list n) | procedure |
| returns: the nth element (zero-based) of list | |
n must be an exact nonnegative integer strictly less than the length of list. list-ref may be defined as follows.
(define list-ref (lambda (ls n) (if (= n 0) (car ls) (list-ref (cdr ls) (- n 1))))) (list-ref '(a b c) 0) ⇒ a (list-ref '(a b c) 1) ⇒ b (list-ref '(a b c) 2) ⇒ c
| (list-tail list n) | procedure |
| returns: the nth tail (zero-based) of list | |
n must be an exact nonnegative integer less than or equal to the length of list. The result is not a copy; the tail is eq? to the nth cdr of list (or to list itself, if n is zero).
list-tail appears in the Revised5 Report but not in the ANSI/IEEE standard. It may be defined as follows.
(define list-tail (lambda (ls n) (if (= n 0) ls (list-tail (cdr ls) (- n 1))))) (list-tail '(a b c) 0) ⇒ (a b c) (list-tail '(a b c) 2) ⇒ (c) (list-tail '(a b c) 3) ⇒ () (list-tail '(a b c . d) 2) ⇒ (c . d) (list-tail '(a b c . d) 3) ⇒ d (let ((x (list 1 2 3))) (eq? (list-tail x 2) (cddr x))) ⇒ #t
| (append list ...) | procedure |
| returns: the concatenation of the input lists | |
append returns a new list consisting of the elements of the first list followed by the elements of the second list, the elements of the third list, and so on. The new list is made from new pairs for all arguments but the last; the last (which need not actually be a list) is merely placed at the end of the new structure. append may be defined as follows.
(define append (lambda args (let f ((ls '()) (args args)) (if (null? args) ls (let g ((ls ls)) (if (null? ls) (f (car args) (cdr args)) (cons (car ls) (g (cdr ls))))))))) (append '(a b c) '()) ⇒ (a b c) (append '() '(a b c)) ⇒ (a b c) (append '(a b) '(c d)) ⇒ (a b c d) (append '(a b) 'c) ⇒ (a b . c) (let ((x (list 'b))) (eq? x (cdr (append '(a) x)))) ⇒ #t
| (reverse list) | procedure |
| returns: a new list containing the elements of list in reverse order | |
reverse may be defined as follows.
(define reverse (lambda (ls) (let rev ((ls ls) (new '())) (if (null? ls) new (rev (cdr ls) (cons (car ls) new)))))) (reverse '()) ⇒ () (reverse '(a b c)) ⇒ (c b a)
| (memq obj list) | procedure |
| (memv obj list) | procedure |
| (member obj list) | procedure |
| returns: the first tail of list whose car is equivalent to obj, or #f | |
These procedures traverse the argument list in order, comparing the elements of list against obj . If an object equivalent to obj is found, the tail of the list whose first element is that object is returned. If the list contains more than one object equivalent to obj, the first tail whose first element is equivalent to obj is returned. If no object equivalent to obj is found, #f is returned. The equivalence test for memq is eq?, for memv is eqv?, and for member is equal?.
These procedures are most often used as predicates, but their names do not end with a question mark because they return a useful true value in place of #t. memq may be defined as follows.
(define memq (lambda (x ls) (cond ((null? ls) #f) ((eq? (car ls) x) ls) (else (memq x (cdr ls))))))
memv and member may be defined similarly, with eqv? and equal? in place of eq?.
(memq 'a '(b c a d e)) ⇒ (a d e) (memq 'a '(b c d e g)) ⇒ #f (memq 'a '(b a c a d a)) ⇒ (a c a d a) (memv 3.4 '(1.2 2.3 3.4 4.5)) ⇒ (3.4 4.5) (memv 3.4 '(1.3 2.5 3.7 4.9)) ⇒ #f (let ((ls (list 'a 'b 'c))) (set-car! (memv 'b ls) 'z) ls) ⇒ (a z c) (member '(b) '((a) (b) (c))) ⇒ ((b) (c)) (member '(d) '((a) (b) (c))) ⇒ #f (member "b" '("a" "b" "c")) ⇒ ("b" "c") (define count-occurrences (lambda (x ls) (cond ((memq x ls) => (lambda (ls) (+ (count-occurrences x (cdr ls)) 1))) (else 0)))) (count-occurrences 'a '(a b c d a))
| (assq obj alist) | procedure |
| (assv obj alist) | procedure |
| (assoc obj alist) | procedure |
| returns: first element of alist whose car is equivalent to obj, or #f | |
The argument alist must be an association list. An association list is a proper list whose elements are key-value pairs of the form (key . value). Associations are useful for storing information (values) associated with certain objects (keys).
These procedures traverse the association list, testing each key for equivalence with obj . If an equivalent key is found, the key-value pair is returned. Otherwise, #f is returned.
The equivalence test for assq is eq?, for assv is eqv?, and for assoc is equal?. assq may be defined as follows.
(define assq (lambda (x ls) (cond ((null? ls) #f) ((eq? (caar ls) x) (car ls)) (else (assq x (cdr ls))))))
assv and assoc may be defined similarly, with eqv? and equal? in place of eq?.
(assq 'b '((a . 1) (b . 2))) ⇒ (b . 2) (cdr (assq 'b '((a . 1) (b . 2)))) ⇒ 2 (assq 'c '((a . 1) (b . 2))) ⇒ #f (assv 2/3 '((1/3 . 1) (2/3 . 2))) ⇒ (2/3 . 2) (assv 2/3 '((1/3 . a) (3/4 . b))) ⇒ #f (assoc '(a) '(((a) . a) (-1 . b))) ⇒ ((a) . a) (assoc '(a) '(((b) . b) (a . c))) ⇒ #f (let ((alist '((2 . a) (3 . b)))) (set-cdr! (assv 3 alist) 'c) alist) ⇒ ((2 . a) (3 . c))
The interpreter given in Section 9.7 represents environments as association lists and uses assq for both variable lookup and assignment.
EAN: 2147483647
Pages: 98