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?
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
