[Haskell-cafe] Collections

[Andrew Coppin]

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.

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.

Why is that, exactly? 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?