Export lists in modules

Cale Gibbard cgibbard at gmail.com
Tue Feb 28 00:33:44 EST 2006

On 23/02/06, John Meacham <john at repetae.net> 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

More information about the Haskell-prime mailing list