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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
