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?