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

[Jonathan Cast]

On Monday 09 July 2007, Dave Bayer wrote:
> 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. This felt like cheating,
> or at least like using a screwdriver as a crowbar, to be less
> judgmental.
>
> Recently I was playing with prime sieves and various heap data
> structures, while rereading Chris Okasaki's "Purely Functional Data
>
> Structures", and it dawned on me:
> > merge xs@(x:xt) ys@(y:yt) = case compare x y of
> >     LT -> x : (merge xt ys)
> >     EQ -> x : (merge xt yt)
> >     GT -> y : (merge xs yt)
> >
> > diff xs@(x:xt) ys@(y:yt) = case compare x y of
> >     LT -> x : (diff xt ys)
> >     EQ -> diff xt yt
> >     GT -> diff xs yt
> >
> > merge' (x:xt) ys = x : (merge xt ys)
> >
> > primes = ps ++ (diff ns $ foldr1 merge' $ map f $ tail primes)
> >     where ps  = [2,3,5]
> >           ns  = [7,9..]
> >           f p = [ m*p | m <- [p,p+2..]]
>
> The code is very fast for its size; I haven't seen Haskell code
> posted on the web that comes close, and it is faster than any of my
> other tries (I posted this code to http://www.haskell.org/haskellwiki/
> Prime_numbers). Effectively, it steals a heap data structure out of
> thin air by exploiting the implementation of lazy evaluation. It
> would seem that GHC's core data structures are coded closer to the
> machine that anything I can write _in_ Haskell. So much for studying
> how to explicitly write a good heap!
>
> So is there a name for this idiom, "no-coding" a classic data
> structure through lazy evaluation? Are there other good examples?

I think we usually call it `exploiting laziness'. . .

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