sjanssen at cse.unl.edu
Tue Jun 19 15:20:35 EDT 2007
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
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
> 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.)
> Haskell-Cafe mailing list
> Haskell-Cafe at haskell.org
More information about the Haskell-Cafe