[Haskell-cafe] Collections

[Spencer Janssen]

On Tue, 19 Jun 2007 19:26:20 +0100
Andrew Coppin <andrewcoppin at btinternet.com> wrote:

> When I was at university, we learned a programming language known as 
> Smalltalk. I was rather good at it. [Ironically, making "small talk"
> is one of the things I do worst IRL! But anyway, back to the topic...]
> 
> In Smalltalk, there is a wide selection of collection types, all with 
> different facilities and efficiency trade offs. There is bag, set,
> list, array, ordered list, dictionary, hash table, weak array, etc. A
> whole menagerie of collection types.

See Edison (http://www.eecs.tufts.edu/~rdocki01/edison.html).  Yes, the
standard library is lacking a few structures (I often miss priority
queues), but the code certainly exists elsewhere.

> However, Haskell only has 1 type of collection: linked lists. (And
> only single-linked at that.) While other "normal" programming
> languages spend huge amounts of effort trying to select exactly the
> right collection type for the task in hand, Haskell programs only
> ever use linked lists.

I think you need to read more Haskell code.  Data.Map and Data.Set
(both tree-based data structures) are used very often.  Arrays exist in
the standard library, but aren't used very often -- O(1) access is
usually not needed and the O(n) update cost for immutable arrays is
quite expensive.  Also, note the wild success of Data.ByteString -- a
structure that is like a weird list/array hybrid.

> Why is that, exactly?

Lists are very handy in a lazy programming language -- Haskell lets us
use lists not only as a data structure, but as control structures as
well.

Also, lists or Data.Map are often "close enough".  Who needs a bag when
"Map a Int" gets the job done?  What good is a heap when Data.Map
supports findMin?


Cheers,
Spencer Janssen

> Does writing software in Haskell magically
> change the properties of these data structures such that lists become
> more efficient than all the other types? Or is it that other data
> structures are only efficient when used with in-place updates? (The
> latter statement appears to be isomorphic to stating that Haskell
> programs must necessarily be less efficient than impure ones.)
> 
> Thoughts?
> 
> _______________________________________________
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell-cafe