23.13 Association lists

An association list (or alist) is a list of pairs. The car of each pair contains a key value, and the cdr contains the associated data value. They can be used to construct simple look–up tables in Scheme. Note that association lists are probably inappropriate for performance–critical use on large data; in these cases, hash tables or some other alternative should be employed.

Function: assoc* key alist

Function: assoc* key alist item=

alist must be an association list: A list of pairs. These procedures find the first pair in alist whose car field is key, and returns that pair. If no pair in alist has key as its car, then #f is returned.

The functions use equal? to compare the keys and they allow the client to pass in an optional equality procedure item= used to compare keys. Notice that assq and assv are exported by (rnrs lists (6)). (vicare-scheme)List utilities.

(assoc* (list 'a) '(((a)) ((b)) ((c))))
⇒ ((a))

The comparison procedure is used to compare the elements Ei of list to the key parameter in this way:

(item= key (car Ei)) ; list is (E1 ... En)

that is, the first argument is always key, and the second argument is one of the list elements. Thus one can reliably find the first entry of alist whose key is greater than five with (assoc* 5 alist <).

Note that fully general alist searching may be performed with the find-tail and find procedures.

Function: alist-cons key obj alist

Defined as:

(lambda (key datum alist)
  (cons (cons key datum) alist))

cons a new alist entry mapping key to obj onto alist.

Function: alist-copy alist

Make a fresh copy of alist. This means copying each pair that forms an association as well as the spine of the list:

(lambda (a)
  (map (lambda (elt)
         (cons (car elt) (cdr elt)))
       a))

Function: alist-delete key alist

Function: alist-delete key alist item=

Function: alist-delete! key alist

Function: alist-delete! key alist item=

Delete all associations from alist with the given key, using the key–comparison procedure item=, which defaults to equal?. The dynamic order in which the various applications of item= are made is not specified.

The returned value may share common tail with alist. The alist is not disordered: Elements that appear in the result alist occur in the same order as they occur in alist.

The comparison procedure is used to compare the element keys Ki of alist’s entries to the key argumentd as (item= key Ki); thus, one can reliably remove all entries of alist whose key is greater than five with (alist-delete 5 alist <).

alist-delete! is allowed to alter cons cells from the alist parameter to construct the result.