[Haskell-cafe] Collections

[Jon Harrop]

I'm not a Haskell guru but I think I can answer this...

On Tuesday 19 June 2007 19:26:20 Andrew Coppin wrote:
> 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.)

I believe you are misinterpreting what you see. Like other modern functional 
languages, Haskell simply provides a different starting point in the context 
of data structures. Singly linked lists are integrated into the language, 
with custom syntax, literals and so forth. This makes them easier to use and, 
consequently, they are more common.

If you choose immutability (which has many benefits) then doubly linked lists 
become comparatively undesirable. In the presence of sum types, pattern 
matching, views, persistence and concurrency, tree-based collections can be 
preferable.

Also, the Haskell standard library appears to include all of the usual data 
structures and many more that are made accessible by functional programming 
and immutability. For example, hash tables, sets and maps:

http://haskell.org/ghc/docs/latest/html/libraries/base/Data-HashTable.html
http://haskell.org/ghc/docs/latest/html/libraries/base/Data-IntMap.html
http://haskell.org/ghc/docs/latest/html/libraries/base/Data-IntSet.html

-- 
Dr Jon D Harrop, Flying Frog Consultancy Ltd.
The OCaml Journal
http://www.ffconsultancy.com/products/ocaml_journal/?e