[Haskell-cafe] Collections

[Chris Kuklewicz]

Andrew Coppin 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.
> 
> 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?

You seem to only bee looking at 2 line long functions in Haskell.

Partly the use of lists comes from the fact that iterating over a sequence of 
values is a very very common operation (the C++ STL's forward iterators; java 
has 'foreach' syntax).  Haskell's lazy list captures this idiom, and the 
compiler can apply useful optimizations (deforesting).

But Haskell does comes with many data structures that most programs use:

http://haskell.org/ghc/docs/latest/html/libraries/ documents what comes with GHC:

Data.ByteString  ( new and very efficient operations )
Data.Sequence    ( based on finger trees )
Data.Tree
Data.HashTable
Data.Map
Data.IntMap
Data.Set
Data.IntSet
Data.PackedString
Data.Queue
Data.Graph

For arrays there are the immutable:
Data.Array
Data.Array.Diff (secretly mutates for efficiency)
Data.Array.Unboxed
And mutable arrays:
Data.Array.IO (boxed and unboxed)
Data.Array.ST (boxed and unboxed)

And for interfacing with the world:
Foreign.Marshal.Array
Data.Array.Storable

http://hackage.haskell.org/packages/archive/pkg-list.html#cat:Data%20Structures 
lists "collections" and "Edison" which both aim to implement a family of 
collections.

And http://haskell.org/haskellwiki/Applications_and_libraries/Data_structures 
has more information on the wiki.

-- 
Chris