I’m continuing this series of posts introducing Lisp to C++ programmers. So, you’ve decided to try your hand at Lisp. You’ve read some introductory book, or looked at your old class notes, and started programming with an editor on the screen and a language reference at hand.
As you go, you pick up some useful functions and techniques, but you probably realise after a while that you’re using maybe fewer than half of the functions defined in the standard. Maybe this is because “there’s more than one way to do it”, but maybe you’re writing code that’s more convoluted than necessary because you haven’t come across the function that would perform in one step what you’re doing in three steps.
I’m going to try to guess at which functions you’ve somehow managed not to run across in your initial programming attempts, and show, with context, what these functions do. I’m not going to be going over functions that are deprecated according to the standard, those really are examples of “more than one way to do it”, and you should try to stick to the non-deprecated functions in new code.
I’m going through these functions in alphabetical order, and the first one that I think might not be have been encountered in a casual introduction to Lisp is acons.
Before I get into this, it’s probably a good idea to review the behaviour of lists in Lisp. Your introduction to Lisp probably showed you the basic model of a list in Lisp. Conceptually, you have a set of cells, each divided into two parts, the car and the cdr. Don’t worry about those strange names, they are, along with cons, actually assembly-language mnemonics for instructions on the old IBM 704 computer that can be used to implement these Lisp operations.
Recalling the descriptions of lists that I laid out in this posting, one way in which you can prepend data to a list is to use the cons function. The acons function is similar, but is specifically designed for use with association lists.
An association list is a particular form of list in Lisp. It is a list of conses, where the car component holds a key and the cdr component holds a value. Here’s how an association list might look:
CL-USER> (let (alist) (setf alist (acons 1 "ONE" alist)) (setf alist (acons 2 "TWO" alist)) (setf alist (acons 3 "THREE" alist)) (plot-lists alist)) ALIST . . ----- ----- ----- |A|D| --> |A|D| --> |A|D| -->NIL ----- ----- ----- | | | | | | | | (1 . ONE) | (2 . TWO) (3 . THREE)
An association list is typically used to accumulate key/value pairs, a bit like a C++ std::map. There are some differences, though:
- Lisp association lists don’t require a weak ordering, as the list is unsorted.
- Consequently, searching is O(N), rather than O(log N) as it is for std::map.
- The first encountered match is returned, so entries can be superseded simply by pushing an entry with a matching key earlier in the list, as long as one remembers that the hidden elements are still there and still affect traversal time.
- Because Lisp isn’t strongly typed, the keys and values can be anything, subject to the restriction that the keys must all be valid inputs to your :test function when looking up values with the assoc function.
Now, acons behaviour can be duplicated with push, as shown here:
CL-USER> (let (alist) (setf alist (acons 1 "ONE" alist)) (setf alist (acons 2 "TWO" alist)) (push (cons 3 "THREE") alist) (plot-lists alist)) ALIST . . ----- ----- ----- |A|D| --> |A|D| --> |A|D| -->NIL ----- ----- ----- | | | | | | | | (1 . ONE) | (2 . TWO) (3 . THREE)
Given this easy substitution, is there any reason to use acons when push does the same thing with fewer keystrokes? Well, that will be a matter of programmer preference. By using acons, you make it obvious that you’re working with an association list, as opposed to another form of list. Personally, I use the push form when I’m programming.