On 23/02/06, John Meacham <[EMAIL PROTECTED]> wrote: > On Thu, Feb 23, 2006 at 10:58:36AM +0000, Malcolm Wallace wrote: > > Some data-structures people (e.g. Chris Okasaki) are of the opinion that > > lists tend to be over-used (because they are built-in), when other > > datatypes might be much more appropriate. > > While this may be true of lesser languages and compilers, for a whole > lot of stuff lists end up faster and more efficient than other data > structures. I know when data.set and data.map first appeared I started > converting things to use them and actually hurt performance in some > cases. unless you can amortize the cost of building a map/set over many > lookups with good coverage and a fair number of values then they tend to > not be worth it. > > I think there are a couple reasons for this: > 4. ghc's list deforestation is friggen awesome. lists are not so much a > data structure in haskell as a programming construct used to express > compositions of routines that work on sequences of items. This alone > makes them quite special and more useful than 'data structures'. >
Exactly. Even without deforestation, in a lazy language, lists are essentially one's loops, or at least, they largely take the place of what one would use loops for in imperative languages. In some sense, lists are the 'simplest' datastructure required to express loops. This is exactly why lists are so common. If people ask why lists are so common in lazy functional languages, they ought also to ask why loops are so common in imperative languages. Such datastructures which are 'universal' in this sense for expressing particular ideas tend to be popular. The Maybe type constructor is so popular because it expresses partiality and nothing more. - Cale _______________________________________________ Haskell-prime mailing list Haskell-prime@haskell.org http://haskell.org/mailman/listinfo/haskell-prime
