What is the relationship between a Lisp "association list" and a key-value mapping like Java's Map?

Question

I'm reading Land of Lisp (which is by the way, one of the best technical books I have ever read) and I have come across the "association list":

(defparameter *edges* 
  '((living-room (garden west door) 
                 (attic upstairs ladder))
    (garden (living-room east door)) 
    (attic (living-room downstairs ladder))))

Is an association list in Lisp the same concept of Java's Map (key-value binding)?

For living-room key, how it is possible to have more than one value? Why enclose the value with a list?

'(living-room
   ((garden west door)
    (attic upstairs ladder)))

Grande

Answer 1

1. Yes, the association list is one way to express key-value associations. Other structures Common Lisp provides to that end are property lists and hash tables.

2. The value is actually already contained in a list. An alist is fundamentally a list of pairs, where the car of each pair is the key, and the cdr is the value associated with that key. If you look up the key LIVING-ROOM with ASSOC and apply CDR to the result:

CL-USER> (cdr (assoc 'living-room *edges*))
((GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER))

The magic behind this lies in the fact that a pair whose car is living-room and whose cdr is a list of the two elements (garden west door) and (attic upstairs ladder) can also be viewed as the three-element list (living-room (garden west door) (attic upstairs ladder)), due to the way lists are constructed out of pairs.

Usually when representing alists as quoted objects, you see the elements depicted explicitly with dotted pairs, rather than punning with list notation, like so:

(defparameter *edges* 
  '((living-room . ((garden west door)
                    (attic upstairs ladder)))
    (garden . ((living-room east door))) 
    (attic . ((living-room downstairs ladder))) ))

Monolingual

Ah, beat me to it by a few minutes! Yes, not using dotted pair syntax threw me for a loop, too, for a second -- good observation! – Wristband

If I want to get the value, why I have to cdr? assoc is supposed to get value, right? – Grande

ASSOC gets you the record. You then need CAR or CDR to get the key/value. – Monolingual

Answer 2

ASSOC returns the cons cell and thus includes both key and value.

The reason is that this makes it easy to update the value (or the key) destructively.

Here the update is hidden behind SETF:

CL-USER 11 > (defparameter *edges* 
               (copy-tree
                '((living-room (garden west door) 
                               (attic upstairs ladder))
                  (garden (living-room east door)) 
                  (attic (living-room downstairs ladder)))))
*EDGES*

CL-USER 12 > (assoc 'living-room *edges*)
(LIVING-ROOM (GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER))

CL-USER 13 > (cdr (assoc 'living-room *edges*))
((GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER))

CL-USER 14 > (setf (cdr (assoc 'living-room *edges*)) '((garden east door)))
((GARDEN EAST DOOR))

CL-USER 15 > (cdr (assoc 'living-room *edges*))
((GARDEN EAST DOOR))

Intelligibility

Answer 3

First, is association list in Lisp the same concept of Java's Map (key-value binding)?

Java's Map is an interface. An alist is a specific way of using a (linked) list to store key-value pairs. I don't think Java has any built-in Maps that have the same properties as an alist, but it wouldn't be hard to write one. Since an alist is a list, all of the functions and properties of lists still hold.

For living-room key, how it is possible to have more than one value? why not to enclose the value with a list:

An alist isn't part of Lisp syntax. It's just a list, so you can put whatever you want in the CDR of each element. In this case, it's another CONS cell. ASSOC just looks at the CAR of each element.

(assoc 'living-room *edges*)
(LIVING-ROOM (GARDEN WEST DOOR) (ATTIC UPSTAIRS LADDER))

Wristband

Answer 4

An association list is similar in concept to a map, insofar as both associate keys with values.

There's no need to enclose multiple values in another list, because that changes the meaning of the value. I'm not familiar with this book, but it seems that the way that *EDGES* is defined, the author wants

(cdr (assoc 'Foobar *edges*))

to be a list of places that you can get from Foobar. As defined, this is true if there are single or multiple values.

If, when there were multiple values, you nested those values in another list, then you'd just have to pick them out of that list when you wanted to use them. It wouldn't give you anything, and it would make it different from the single value case.

Overreach