common-lisp Types of Lists Association Lists

Example

Plain lists are useful for representing a sequence of elements, but sometimes it is more helpful to represent a kind of key to value mapping. Common Lisp provides several ways to do this, including genuine hash tables (see 18.1 Hash Table Concepts). There are two primary ways or representing key to value mappings in Common Lisp: property lists and association lists. This example describes association lists.

An association list, or alist is a "plain" list whose elements are dotted pairs in which the car of each pair is the key and the cdr of each pair is the associated value. For instance,

(defparameter *ages* (list (cons 'john 34) (cons 'mary 23) (cons 'tim 72)))

can be considered as an association list that maps symbols indicating a personal name with an integer indicating age. It is possible to implement some retrieval functions using plain list functions, like member. For instance, to retrieve the age of john, one could write

(cdr (first (member 'mary *age* :key 'car)))
;=> 23

The member function returns the tail of the list beginning with with a cons cell whose car is mary, that is, ((mary . 23) (tim . 72)), first returns the first element of that list, which is (mary . 23), and cdr returns the right side of that pair, which is 23. While this is one way to access values in an association list, the purpose of a convention like association lists is to abstract away from the underlying representation (a list) and to provide higher-level functions for working with the data structure.

For association lists, the retrieval function is assoc, which takes a key, an association list and optional testing keywords (key, test, test-not), and returns the pair for the corresponding key:

(assoc 'tim *ages*)
;=> (tim . 72)

Since the result will always be a cons cell if an item is present, if assoc returns nil, then the item was not in the list:

(assoc 'bob *ages*)
;=> nil

For updating values in an association list, setf may be used along with cdr. For instance, when john's birthday arrives and his age increases, either of the following could be performed:

(setf (cdr (assoc 'john *ages*) 35)

(incf (cdr (assoc 'john *ages*)))

incf works in this case because it is based on setf.

Association lists can also be used as a type of bidirectional map, since key to value mappings be retrieved based on the value by using the reversed assoc function, rassoc.

In this example, the association list was created by using list and cons explicitly, but association lists can also be created by using pairlis, which takes a list of keys and data and creates an association list based on them:

(pairlis '(john mary tim) '(23 67 82))
;=> ((john . 23) (mary . 67) (tim . 82))

A single key and value pair can be added to an association list using acons:

(acons 'john 23 '((mary . 67) (tim . 82)))
;=> ((john . 23) (mary . 67) (tim . 82))

The assoc function searches through the list from left to right, which means that is is possible to "mask" values in an association list without removing them from a list or updating any of the structure of the list, just by adding new elements to the beginning of the list. The acons function is provided for this:

(defvar *ages* (pairlis '(john mary tim) '(34 23 72)))

(defvar *new-ages* (acons 'mary 29 *ages*))

*new-ages*
;=> ((mary . 29) (john . 34) (mary . 23) (tim . 72))

And now, a lookup for mary will return the first entry:

(assoc 'mary *new-ages*)
;=> 29