(lispref.info)Association Lists


Prev: Sets And Lists Up: Lists

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".
(This usage of "key" is not related to the term "key sequence"; it
means any object which can be looked up in a table.)

   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 Emacs 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.  Note: 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' (*note
     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: 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.  Note: Equality Predicates.

          (setq trees '((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 the CDR of the ALIST
     associations is tested 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 be used to 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 can be seen
     more clearly if the association is written in dotted pair notation:

          (lily white) == (lily . (white))

 - 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


automatically generated by info2www