Next: Hash Tables Up: Lists Previous: Using Lists as
Common Lisp the Language, 2nd Edition
Next: Hash Tables
Up: Lists
Previous: Using Lists as
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]
aconskeydatuma-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]
pairliskeysdata&optionala-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]
associtema-list&key :test :test-not :key
assoc-ifpredicatea-list
assoc-if-notpredicatea-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-ifpredicatea-list&key :key
assoc-if-notpredicatea-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) nowA 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]
rassocitema-list&key :test :test-not :key
rassoc-ifpredicatea-list
rassoc-if-notpredicatea-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-ifpredicatea-list&key :key
rassoc-if-notpredicatea-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
AI.Repository@cs.cmu.edu