11.8 Association Lists

An association list, or alist for short, records a mapping from keys to values. It is a list of cons cells called associations: the CAR of each cell is the key, and the CDR is the associated value.¹

Here is an example of an alist. The key pine is associated with the value cones; the key oak is associated with acorns; and the key maple is associated with seeds.

'((pine . cones)
  (oak . acorns)
  (maple . seeds))

The associated values in an alist may be any Lisp objects; so may the keys. For example, in the following alist, the symbol a is associated with the number 1, and the string "b" is associated with the list (2 3), which is the CDR of the alist element:

((a . 1) ("b" 2 3))

Sometimes it is better to design an alist to store the associated value in the CAR of the CDR of the element. Here is an example:

'((rose red) (lily white) (buttercup yellow))

Here we regard red as the value associated with rose. One advantage of this method is that you can store other related information—even a list of other items—in the CDR of the CDR. One disadvantage is that you cannot use rassq (see below) to find the element containing a given value. When neither of these considerations is important, the choice is a matter of taste, as long as you are consistent about it for any given alist.

Note that the same alist shown above could be regarded as having the associated value in the CDR of the element; the value associated with rose would be the list (red).

Association lists are often used to record information that you might otherwise keep on a stack, since new associations may be added easily to the front of the list. When searching an association list for an association with a given key, the first one found is returned, if there is more than one.

In SXEmacs Lisp, it is not an error if an element of an association list is not a cons cell. The alist search functions simply ignore such elements. Many other versions of Lisp signal errors in such cases.

Note that property lists are similar to association lists in several respects. A property list behaves like an association list in which each key can occur only once. See Property Lists, for a comparison of property lists and association lists.

Function: assoc key alist

This function returns the first association for key in alist. It compares key against the alist elements using equal (see Equality Predicates). It returns nil if no association in alist has a CAR equal to key. For example:

(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     ⇒ ((pine . cones) (oak . acorns) (maple . seeds))
(assoc 'oak trees)
     ⇒ (oak . acorns)
(cdr (assoc 'oak trees))
     ⇒ acorns
(assoc 'birch trees)
     ⇒ nil

Here is another example, in which the keys and values are not symbols:

(setq needles-per-cluster
      '((2 "Austrian Pine" "Red Pine")
        (3 "Pitch Pine")
        (5 "White Pine")))

(cdr (assoc 3 needles-per-cluster))
     ⇒ ("Pitch Pine")
(cdr (assoc 2 needles-per-cluster))
     ⇒ ("Austrian Pine" "Red Pine")

Function: rassoc value alist

This function returns the first association with value value in alist. It returns nil if no association in alist has a CDR equal to value.

rassoc is like assoc except that it compares the CDR of each alist association instead of the CAR. You can think of this as “reverse assoc”, finding the key for a given value.

Function: assq key alist

This function is like assoc in that it returns the first association for key in alist, but it makes the comparison using eq instead of equal. assq returns nil if no association in alist has a CAR eq to key. This function is used more often than assoc, since eq is faster than equal and most alists use symbols as keys. See Equality Predicates.

(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))
     ⇒ ((pine . cones) (oak . acorns) (maple . seeds))
(assq 'pine trees)
     ⇒ (pine . cones)

On the other hand, assq is not usually useful in alists where the keys may not be symbols:

(setq leaves
      '(("simple leaves" . oak)
        ("compound leaves" . horsechestnut)))

(assq "simple leaves" leaves)
     ⇒ nil
(assoc "simple leaves" leaves)
     ⇒ ("simple leaves" . oak)

Function: rassq value alist

This function returns the first association with value value in alist. It returns nil if no association in alist has a CDR eq to value.

rassq is like assq except that it compares the CDR of each alist association instead of the CAR. You can think of this as “reverse assq”, finding the key for a given value.

For example:

(setq trees '((pine . cones) (oak . acorns) (maple . seeds)))

(rassq 'acorns trees)
     ⇒ (oak . acorns)
(rassq 'spores trees)
     ⇒ nil

Note that rassq cannot search for a value stored in the CAR of the CDR of an element:

(setq colors '((rose red) (lily white) (buttercup yellow)))

(rassq 'white colors)
     ⇒ nil

In this case, the CDR of the association (lily white) is not the symbol white, but rather the list (white). This becomes clearer if the association is written in dotted pair notation:

(lily white) ≡ (lily . (white))

Function: remassoc key alist

This function deletes by side effect any associations with key key in alist—i.e. it removes any elements from alist whose car is equal to key. The modified alist is returned.

If the first member of alist has a car that is equal to key, there is no way to remove it by side effect; therefore, write (setq foo (remassoc key foo)) to be sure of changing the value of foo.

Function: remassq key alist

This function deletes by side effect any associations with key key in alist—i.e. it removes any elements from alist whose car is eq to key. The modified alist is returned.

This function is exactly like remassoc, but comparisons between key and keys in alist are done using eq instead of equal.

Function: remrassoc value alist

This function deletes by side effect any associations with value value in alist—i.e. it removes any elements from alist whose cdr is equal to value. The modified alist is returned.

If the first member of alist has a car that is equal to value, there is no way to remove it by side effect; therefore, write (setq foo (remassoc value foo)) to be sure of changing the value of foo.

remrassoc is like remassoc except that it compares the CDR of each alist association instead of the CAR. You can think of this as “reverse remassoc”, removing an association based on its value instead of its key.

Function: remrassq value alist

This function deletes by side effect any associations with value value in alist—i.e. it removes any elements from alist whose cdr is eq to value. The modified alist is returned.

This function is exactly like remrassoc, but comparisons between value and values in alist are done using eq instead of equal.

Function: copy-alist alist

This function returns a two-level deep copy of alist: it creates a new copy of each association, so that you can alter the associations of the new alist without changing the old one.

(setq needles-per-cluster
      '((2 . ("Austrian Pine" "Red Pine"))
        (3 . ("Pitch Pine"))

        (5 . ("White Pine"))))
⇒
((2 "Austrian Pine" "Red Pine")
 (3 "Pitch Pine")
 (5 "White Pine"))

(setq copy (copy-alist needles-per-cluster))
⇒
((2 "Austrian Pine" "Red Pine")
 (3 "Pitch Pine")
 (5 "White Pine"))

(eq needles-per-cluster copy)
     ⇒ nil
(equal needles-per-cluster copy)
     ⇒ t
(eq (car needles-per-cluster) (car copy))
     ⇒ nil
(cdr (car (cdr needles-per-cluster)))
     ⇒ ("Pitch Pine")

(eq (cdr (car (cdr needles-per-cluster)))
    (cdr (car (cdr copy))))
     ⇒ t

This example shows how copy-alist makes it possible to change the associations of one copy without affecting the other:

(setcdr (assq 3 copy) '("Martian Vacuum Pine"))
(cdr (assq 3 needles-per-cluster))
     ⇒ ("Pitch Pine")