[Haskell-cafe] "no-coding" functional data structures via lazyness

Dave Bayer bayer at cpw.math.columbia.edu
Tue Jul 10 01:36:40 EDT 2007

On Jul 9, 2007, at 6:52 PM, Donald Bruce Stewart wrote:

> bayer:
>> Learning Haskell, the Prelude.ShowS type stood out as odd, exploiting
>> the implementation of lazy evaluation to avoid explicitly writing an
>> efficient concatenable list data structure.

> See also
>     http://hackage.haskell.org/cgi-bin/hackage-scripts/package/ 
> dlist-0.3

Thanks; I added a link to the dlist package from my discussion of  
this idiom on the Wiki page

On Jul 9, 2007, at 3:19 PM, Jonathan Cast wrote:
> I think we usually call it `exploiting laziness'. . .

My motivation in asking for a name was to be able to find other  
Haskell one-liners adequately replacing chapters of data structure  
books for problems of modest scale, e.g. finding the 5,000,000th  
prime. So far, I know concatenable lists, and heaps.  Is there a Wiki  
page where someone teaches this principle for a dozen other classic  
data structures? Your "one-liner" made me laugh, but it didn't help  
me in googling, I would have preferred a one-liner teaching me  
another classic data structure, or an explanation of why burrowing  
into the GHC implementation gives such a speed advantage over a  
carefully written explicit data structure.

People in other camps don't really "get" lazy evaluation, even many  
of our ML neighbors. It would pay to communicate this better to the  
outside world.

More information about the Haskell-Cafe mailing list