Association List

An AssociationList, or AyList?, is a DesignPattern for generating associative data structures in LispLanguage. Early dialects of Lisp had lists as the only data structure; there was no low-level support for associative containers (modern versions of Lisp such as CommonLisp have hash-tables and the like). An a-list consists of a list of associations, or key/value pairs. Such a list pairing the letters of the alphabet with their value in ScrabbleGame? might look like this:

 ( (A 1) (B 3) (C 3) (D 2) (E 1) (F 4) (G 2) (H 4) (I 1) (J 8) (K 5) (L 1) (M 3)
   (N 1) (O 1) (P 3) (Q 10) (R 1) (S 1) (T 1) (U 1) (V 4) (W 4) (X 8) (Y 4) (Z 10) )

Alists have the advantage of being simple to represent and understand. They have the disadvantage of requiring O(N) time (average case) to retrieve any particular key, where N is the size of the list, even if stored in a sorted order (assuming they are implemented as a traditional LispLanguage list). Compare this to sorted arrays and balanced trees (which require O(ln N) time) or hashtables (which require O(1) time on average, though O(N) time worst case).

Note that CommonLisp also has hash tables as part of the standard set of data structures available so alists are not used instead of hash tables but in certain situations where some of their particular characteristics make them appropriate.

Of course, if you iterate through a complete list and don't care about the order; AyList?s are just as fast as any of the other data structures used for associative arrays--faster, in fact, because the overhead of traversing an a-list is smaller than the overhead needed to traverse a tree or hashtable. Many Lisp programs do exactly that.

Alists also have a feature not that hash tables do not: you can "shadow" values in an alist. For example if you have the alist:

 ((A 1) (B 2) (C 3))

and then you want to temporarily give C the value 4, you can (in Lisp) create a new alist:

  (setf the-alist (acons 'C 4 the-alist))

When you want to remove the shadowing value for C you say:

  (setf the-alist (rest the-alist)) ;; or (pop the-alist)

Of course, you can do that with HashTables too; assuming the hashtable is designed with that in mind. A common implementation of a HashTable is an array of LinkedLists; one list for each hash bucket. Since elements with the same key hash to the same bucket; all you need is a hashtable which appends duplicate keys to the head of the appropriate list, rather than replacing or returning an error if a duplicate key is ever inserted. Likewise, said table should remove the first matching element it finds in a remove operation, rather than all of them.

How USEFUL this operation is, I'm not entirely sure. The particular hack described above certainly has a bit of CodeSmell about it, at least to my nose. In addition, if you iterate over a list modified as above, won't you see BOTH elements with C as a key?????

--ScottJohnson

Sure. As I explained recently on the LispQuestions page in response to some other questions about alists, they're really not the end-all-be-all of mapping data structures in Common Lisp. If you want a hash table, Common Lisp has hash tables. If there is probably a code smell to be associated (no pun intended) with alists, it would be using them when one really wants a hash table. They aren't objects, they are a composite arrangement of ConsCell objects and some functions for manipulating them. They probably exist because they were a fairly easy way to implement dynamic bindings of variables in early Lisp interpreters (circa 1956) when you already had a ConsCell as one of your basic data types. They are still sometimes useful for that kind of dynamic binding. For example:

  (defun run-function-with-new-binding (name value function bindings)
     ;; bindings is an alist, i.e. a cons cell that happens to be the head of an alist
     ;; function is a function that we're about to call. When we invoke it we will be passing it a 
     ;; Set of bindings that includes all the ones that were passed to us, plus the new name/value pair
     ;; which may shadow an existing binding for that name. But we are not modifying the bindings list
     ;; that was passed to us, which our caller will probably appreciate. When the funcall returns
     ;; the extra cons cells created to hold the new binding get gc'd and we return to our caller. 
     (funcall function (acons name value bindings)))

--PeterSeibel

Why would you want to use an AssociationList instead of a map?

If you 're implementing something like the code above (which is likely if you are implementing an interpreter for a language with dynamically scoped variables) an alist is one simple implementation strategy for holding the bindings. Also, if you just need a small number of key/value pairs, an alist is probably more efficient than a hash table because the difference between O(N) and approx O(1) gets lost in the constant factors--ConsCells are one of the smallest, lightest weight data structures in Lisp and an alist is just a handful of them pointing to each other.

So it sounds like you would use an AssociationList when you want the shadowing behavior. I still don't know why you would want the shadowing behavior. I've never found myself wishing I could obscure one element of a list with another temporarily. Can you explain the motivation behind this?

Suppose you were writing an HTML renderer that understands CSS styles. So you have to parse an HTML document and keep track of what styles are currently in effect. Since HTML elements can nest and can each provide their own values for various parts of the style, the values can be shadowed. For instance, a BODY element with the font-family style of sans-serif means that unless otherwise specified all elements contained in the BODY should be rendered in sans-serif. But if a P inside the BODY explicitly sets the font-family to times-roman you need to make "times-roman" the value under the "font-family" until you're done rendering the P element and all it's children. (Unless, of course the children further shadow it by providing their own value for "font-family".) Once the P element is rendered, the rest of the children of BODY need to be rendered with "font-family" back to "sans-serif". One way or another you're going to need a data structure that allows you to keep track of a stack of values for a bunch of keys. In Lisp, it's particularly easy to implement that structure with an alist. Similar problems come up with writing interpreters and compilers for programming languages that allow variables to be shadowed.