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

[Dave 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. 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?