11.1 Association Lists

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.¹¹

procedure: alist? object

Returns #t if object is an association list (including the empty list); otherwise returns #f. Any object satisfying this predicate also satisfies list?.

procedure: assq object alist

procedure: assv object alist

procedure: assoc object alist

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 uses eq? to compare object with the car fields of the pairs in alist, while assv uses eqv? and assoc uses equal?.¹²

(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)

procedure: association-procedure predicate selector

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))

procedure: del-assq object alist

procedure: del-assv object alist

procedure: del-assoc object alist

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 uses eq? to compare object with the keys, while del-assv uses eqv? and del-assoc uses equal?.

(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."))

procedure: del-assq! object alist

procedure: del-assv! object alist

procedure: del-assoc! object alist

These procedures remove from alist all associations with keys equal to object. They return the resulting list. del-assq! uses eq? to compare object with the keys, while del-assv! uses eqv? and del-assoc! uses equal?. These procedures are like del-assq, del-assv, and del-assoc, respectively, except that they destructively modify alist.

procedure: delete-association-procedure deletor predicate selector

This returns a deletion procedure similar to del-assv or 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 del-assv:

(define del-assv 
  (delete-association-procedure list-deletor eqv? car))

procedure: alist-copy alist

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)))))