On Tue, 19 Jun 2007 19:26:20 +0100 Andrew Coppin <[EMAIL PROTECTED]> 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 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 > [email protected] > http://www.haskell.org/mailman/listinfo/haskell-cafe _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
