CODEWITHSUNDEEP
c#lispcommon-lisp
alexandrekow
alexandrekow

Reputation: 1937

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

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?

Upvotes: 3

Views: 1070

Answers (5)

Vsevolod Dyomkin
Vsevolod Dyomkin

Reputation: 9451

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.

Upvotes: 8

C. K. Young
C. K. Young

Reputation: 223133

Comparisons between alists and hash tables (which Dictionary uses), since nobody seems to have touched on this yet:

Alists:

  • Are simple to implement (just a list of pairs)
  • Have linear-time lookup (thus only useful for small lists)

Hash tables:

  • Take a little more effort to implement (in particular, you must implement a stable hash function for keys)
  • Have amortised constant-time lookup

Upvotes: 2

Scott Rippey
Scott Rippey

Reputation: 15810

Yes, they are very similar and serve a similar purpose, but there is at least one significant difference:

A .NET Dictionary cannot have multiple items with the same key!

Apparently, an alist can:

When searching an association list for an association with a given key, the first one found is returned, if there is more than one.

Upvotes: 0

Rainer Joswig
Rainer Joswig

Reputation: 139311

It's a mapping from keys to values. So it can act similar to a dictionary. During the evolution of Lisp, hash-tables have been added, which serve a similar purpose.

Upvotes: 0

BillRobertson42
BillRobertson42

Reputation: 12883

Yes, its pretty much the same thing. Also called associative arrays (perl) and maps (java and others).

Upvotes: -1

Related Questions