Is an association list in LISP the same thing as a Dictionary in C#?

Question

I am reading a book about Common LISP and the author says : "An alist consists of key/value pairs stored in a list."

So it made me think, is this the same thing as a Dictionnary in C# or not? If so why?

Answer 1

There is a distinction between abstract concepts and concrete data-structures.

A dictionary is an abstract concept - a mapping of keys to values. It can be implemented with several different approaches:

• as a list: of key-value pairs (Lisp's alists), a flat list of interleaved keys and values (Lisp's plists), as a pair of two lists of keys and values
• as a table, be it Lisp's hash-table/Java's HashMap or some other kind of table
• as a tree (Java's TreeMap)
• etc

C#'s Dictionary is a data-structure that supports (amortized) constant lookup time, like CL's hash-table. In this regard it is different from alist, that has linear lookup time. Also alists don't depend on element's hash-code in order to store/retrieve it. The API of alists is also different, than Dictionary's. There's assoc and rassoc to lookup an element from the left side and right side respectively. (So, unlike in a conventional dictionary, there can be multiple mappings of the same key to different values in an alist). Also there are acons and pairlis to construct an alist.

EDIT And, finally, there's no standard function to remove an item from alist. You can delete an element with (remove key alist :key #'car). But note, that this operation leaves the original list intact and returns a modified list as a result.