On Tue, 19 Jun 2007 19:26:20 +0100
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.
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 well. 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 supports findMin? Cheers, Spencer Janssen
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?
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe