Music 220b: Winter 2001
Fernando Lopez-Lezcano, instructor
Christopher Burns, teaching assistant
Tamara Smyth, teaching assistant
Week 4: (cons) and association lists
Association lists are a variant of the standard Lisp data type with some useful properties. We can use association lists to make simple (and not-so-simple) databases -- the trick is to associate a key with its data, and then retrieve the data by reference to the key.
Before we look at association lists there's a fundamental list-making function we should look at: (cons).
(cons)
The function (cons) is Lisp's primitive for constructing lists. (Cons) takes two elements and binds them together in a pair. Remember that every list is made of pairs; the first element holds some item, and the second element points to the next pair in the list. (Cons) is the underlying way in which lists are constructed -- so
(list 1 2 3 4)
is equivalent to:
(cons 1 (cons 2 (cons 3 (cons 4 nil))))
What happens if we put data in both elements of the cons pair? We get an association list.
Association lists
Association lists are lists which include two-element conses. Two-element conses are also known as dotted pairs, because of this interpreter behavior:
CM(1): (cons 'a 'b) (A . B)
A typical association list might look like this association between musical note-names and frequencies in Hertz:
(cons (cons 'a4 440) (cons (cons 'b4 493) nil))
Or, in shorter form:
'((a4 . 440) (b4 . 493))
Now we can use the (assoc) and (rassoc) functions to retrieve these associations. (assoc key association-list) returns the dotted pair whose first element corresponds to key; (rassoc datum association-list) returns the dotted pair whose second element corresponds to datum. These functions search from the beginning of the association list -- if you use the same key several times then (assoc) will return the first instance in the list. (This is a feature if you want to non-destructively update your association list).
Since we already have the key we're searching for, we usually just want the datum (second element of the dotted pair), which we can get with:
(cdr (assoc key association-list))
If there is no matching key then (assoc) will return nil; the (cdr) of nil is nil. (Any dotted pairs with nil as their second value will also return nil....)
For an example of an association list in action, see the generic state machine.