Next: 1D Tables, Previous: Associations, Up: Associations
An association list, or alist, is a data structure used very frequently in Scheme. An alist is a list of pairs, each of which is called an association. The car of an association is called the key.
An advantage of the alist representation is that an alist can be
incrementally augmented simply by adding new entries to the front.
Moreover, because the searching procedures assv
et al. search the
alist in order, new entries can “shadow” old entries. If an alist is
viewed as a mapping from keys to data, then the mapping can be not only
augmented but also altered in a non-destructive manner by adding new
entries to the front of the alist.1
Returns
#t
if object is an association list (including the empty list); otherwise returns#f
. Any object satisfying this predicate also satisfieslist?
.
These procedures find the first pair in alist whose car field is object, and return that pair; the returned pair is always an element of alist, not one of the pairs from which alist is composed. If no pair in alist has object as its car,
#f
(n.b.: not the empty list) is returned.assq
useseq?
to compare object with the car fields of the pairs in alist, whileassv
useseqv?
andassoc
usesequal?
.2(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)
Returns an association procedure that is similar to
assv
, except that selector (a procedure of one argument) is used to select the key from the association, and predicate (an equivalence predicate) is used to compare the key to the given item. This can be used to make association lists whose elements are, say, vectors instead of pairs (also see Searching Lists).For example, here is how
assv
could be implemented:(define assv (association-procedure eqv? car))Another example is a “reverse association” procedure:
(define rassv (association-procedure eqv? cdr))
These procedures return a newly allocated copy of alist in which all associations with keys equal to object have been removed. Note that while the returned copy is a newly allocated list, the association pairs that are the elements of the list are shared with alist, not copied.
del-assq
useseq?
to compare object with the keys, whiledel-assv
useseqv?
anddel-assoc
usesequal?
.(define a '((butcher . "231 e22nd St.") (baker . "515 w23rd St.") (hardware . "988 Lexington Ave."))) (del-assq 'baker a) => ((butcher . "231 e22nd St.") (hardware . "988 Lexington Ave."))
These procedures remove from alist all associations with keys equal to object. They return the resulting list.
del-assq!
useseq?
to compare object with the keys, whiledel-assv!
useseqv?
anddel-assoc!
usesequal?
. These procedures are likedel-assq
,del-assv
, anddel-assoc
, respectively, except that they destructively modify alist.
This returns a deletion procedure similar to
del-assv
ordel-assq!
. The predicate and selector arguments are the same as those forassociation-procedure
, while the deletor argument should be either the procedurelist-deletor
(for non-destructive deletions), or the procedurelist-deletor!
(for destructive deletions).For example, here is a possible implementation of
del-assv
:(define del-assv (delete-association-procedure list-deletor eqv? car))
Returns a newly allocated copy of alist. This is similar to
list-copy
except that the “association” pairs, i.e. the elements of the list alist, are also copied.alist-copy
could have been implemented like this:(define (alist-copy alist) (if (null? alist) '() (cons (cons (car (car alist)) (cdr (car alist))) (alist-copy (cdr alist)))))