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.11
#t if object is an association list (including the
empty list); otherwise returns
#f. Any object satisfying this
predicate also satisfies
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
#f (n.b.: not the empty list) is returned.
eq? to compare object with the car fields of the pairs
in alist, while
(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
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.
eq? to compare
object with the keys, while
(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.
eq? to compare object with the keys,
equal?. These procedures are like
del-assoc, respectively, except that they
destructively modify alist.
This returns a deletion procedure similar to
del-assq!. The predicate and selector arguments are
the same as those for
association-procedure, while the
deletor argument should be either the procedure
list-deletor (for non-destructive deletions), or the procedure
list-deletor! (for destructive deletions).
For example, here is a possible implementation of
(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.
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)))))
This introduction is taken from Common Lisp, The Language, second edition, p. 431.
Although they are often used as predicates,
assoc do not have question marks in
their names because they return useful values rather than just