Common Lisp the Language, 2nd Edition
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.
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.