Common Lisp the Language, 2nd Edition

Next: Hash Tables Up: Lists Previous: Using Lists as

# 15.6. Association Lists

An association list, or a-list, is a data structure used very frequently in Lisp. An a-list is a list of pairs (conses); each pair is an association. The car of a pair is called the key, and the cdr is called the datum.

An advantage of the a-list representation is that an a-list can be incrementally augmented simply by adding new entries to the front. Moreover, because the searching function `assoc` searches the a-list in order, new entries can ``shadow'' old entries. If an a-list 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 a-list.

Sometimes an a-list represents a bijective mapping, and it is desirable to retrieve a key given a datum. For this purpose, the ``reverse'' searching function `rassoc` is provided. Other variants of a-list searches can be constructed using the function `find` or `member`.

It is permissible to let `nil` be an element of an a-list in place of a pair. Such an element is not considered to be a pair but is simply passed over when the a-list is searched by `assoc`.

[Function]
`acons key datum a-list`

`acons` constructs a new association list by adding the pair `(key . datum)` to the old a-list.

    (acons x y a) == (cons (cons x y) a)

This is a trivial convenience function, but I find I use it a lot.

[Function]
`pairlis keys data &optional a-list`

`pairlis` takes two lists and makes an association list that associates elements of the first list to corresponding elements of the second list. It is an error if the two lists keys and data are not of the same length. If the optional argument a-list is provided, then the new pairs are added to the front of it.

The new pairs may appear in the resulting a-list in any order; in particular, either forward or backward order is permitted. Therefore the result of the call

    (pairlis '(one two) '(1 2) '((three . 3) (four . 19)))

might be

    ((one . 1) (two . 2) (three . 3) (four . 19))

but could equally well be

    ((two . 2) (one . 1) (three . 3) (four . 19))

[Function]
`assoc item a-list &key :test :test-not :key
``assoc-if predicate a-list
``assoc-if-not predicate a-list`

X3J13 voted in March 1988 (ASSOC-RASSOC-IF-KEY) to allow `assoc-if` and `assoc-if-not` also to take a keyword argument named `:key`, to be used to determine whether a pair ``satisfies the test'' in the same manner as for sequence functions. The new function descriptions are therefore as follows:

[Function]
`assoc-if predicate a-list &key :key
``assoc-if-not predicate a-list &key :key`

The omission of `:key` arguments for these functions in the first edition was probably an oversight.

Each of these searches the association list a-list. The value is the first pair in the a-list such that the car of the pair satisfies the test, or `nil` if there is no such pair in the a-list. For example:

    (assoc 'r '((a . b) (c . d) (r . x) (s . y) (r . z)))
            =>  (r . x)
    (assoc 'goo '((foo . bar) (zoo . goo))) => nil
    (assoc '2 '((1 a b c) (2 b c d) (-7 x y z))) => (2 b c d)

It is possible to `rplacd` the result of `assoc` provided that it is not `nil`, in order to ``update'' the ``table'' that was `assoc`'s second argument. (However, it is often better to update an a-list by adding new pairs to the front, rather than altering old pairs.) For example:

    (setq values '((x . 100) (y . 200) (z . 50)))
    (assoc 'y values) => (y . 200)
    (rplacd (assoc 'y values) 201)
    (assoc 'y values) => (y . 201) now

A typical trick is to say `(cdr (assoc x y))`. Because the cdr of `nil` is guaranteed to be `nil`, this yields `nil` if no pair is found or if a pair is found whose cdr is `nil`. This is useful if `nil` serves its usual role as a ``default value.''

The two expressions

    (assoc item list :test fn)

and

    (find item list :test fn :key #'car)

are equivalent in meaning with one important exception: if `nil` appears in the a-list in place of a pair, and the item being searched for is `nil`, `find` will blithely compute the car of the `nil` in the a-list, find that it is equal to the item, and return `nil`, whereas `assoc` will ignore the `nil` in the a-list and continue to search for an actual pair (cons) whose car is `nil`. See `find` and `position`.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

Compatibility note: In MacLisp, the `assoc` function uses an `equal` comparison rather than `eql`, which is the default test for `assoc` in Common Lisp. Where in MacLisp one would write `(assoc x y)`, in Common Lisp one must write `(assoc x y :test #'equal)` to get the completely identical effect. Similarly, one can get the precise effect, and no more, of the MacLisp `(assq x y)` by writing in Common Lisp `(assoc x y :test #'eq)`.

In Interlisp, `assoc` uses an `eq` test, and `sassoc` uses an Interlisp `equal` test.

[Function]
`rassoc item a-list &key :test :test-not :key
``rassoc-if predicate a-list
``rassoc-if-not predicate a-list`

X3J13 voted in March 1988 (ASSOC-RASSOC-IF-KEY) to allow `rassoc-if` and `rassoc-if-not` also to take a keyword argument named `:key`, to be used to determine whether a pair ``satisfies the test'' in the same manner as for sequence functions. The new function descriptions are therefore as follows:

[Function]
`rassoc-if predicate a-list &key :key
``rassoc-if-not predicate a-list &key :key`

The omission of `:key` arguments for these functions in the first edition was probably an oversight.

`rassoc` is the reverse form of `assoc`; it searches for a pair whose cdr satisfies the test, rather than the car. If the a-list is considered to be a mapping, then `rassoc` treats the a-list as representing the inverse mapping. For example:

    (rassoc 'a '((a . b) (b . c) (c . a) (z . a))) => (c . a)

The expressions

    (rassoc item list :test fn)

and

    (find item list :test fn :key #'cdr)

are equivalent in meaning, except when the item is `nil` and `nil` appears in place of a pair in the a-list. See the discussion of the function `assoc`.

X3J13 voted in January 1989 (MAPPING-DESTRUCTIVE-INTERACTION) to restrict user side effects; see section 7.9.

Next: Hash Tables Up: Lists Previous: Using Lists as