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
_______________________________________________
Haskell-Cafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskell-cafe
