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

[Jonathan Cast]

On Tuesday 10 July 2007, Dave Bayer wrote:
> 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
> 	http://www.haskell.org/haskellwiki/Prime_numbers
>
> 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.

Unfortunately, I'm afraid all I can do at this point is wish you luck in your 
search.

Jonathan Cast
http://sourceforge.net/projects/fid-core
http://sourceforge.net/projects/fid-emacs