Association lists

Association lists

Association lists are a simple key/value data structure, consisting of a list of pairs. Keys are looked up in the association list by linearly scanning the list, which makes association lists inefficient for large numbers of entries. Arc's tables are an alternative to association lists. Some advantages of association lists are that they can preserve order and preserve old values. Also, multiple association lists can share the same tail.

For more information on association lists, see Common Lisp the Language. Unlike Common Lisp association lists that are built out of dotted pairs, Arc association lists are built out of list pairs.

Arc includes functions for looking up keys in an association list, but no explicit support for building association lists. The lists, however, are simple to create and extend:

arc> (= al '((key1 val1) (key2 val2)))
((key1 val1) (key2 val2))
arc> (push '(key3 val3) al)
((key3 val3) (key1 val1) (key2 val2))
arc> (alref al 'key1)

alref al key
Looks up key in association list al. Returns the value or nil.
>(alref '((k1 v1) (k2 v2)) 'k1)
>(alref '((k1 v1) (k2 v2)) 'foo)
assoc key al
Looks up key in association list al. Returns the key/value pair or nil. Note that assoc and alref reverse the order of the arguments.
>(assoc 'k1 '((k1 v1) (k2 v2)))
(k1 v1)
>(assoc 'foo '((k1 v1) (k2 v2)))

Copyright 2008 Ken Shirriff.