Heinrich Apfelmus
Leon Smith wrote:
[1] http://permalink.gmane.org/gmane.comp.lang.haskell.cafe/84666 [2] http://apfelmus.nfshost.com/articles/implicit-heaps.html [3]
http://hackage.haskell.org/packages/archive/data-ordlist/0.4.4/doc/html/Data...
List-Ordered.html#v:mergeAll
Will Ness
primes = 2: primes' where primes' = 3: 5: [7,9..] `minus` tfold [ [p*p,p*p+2*p..] | p <- primes' ] tfold ((x:xs):t) = x : xs `union` tfold (pairs t) pairs ((x:xs):ys:t) = (x: union xs ys) : pairs t
Unfortunately, it turns out that this program is clear, shorter ... and subtly wrong. :)
Here an example where the VIP merge would give a different result
bad = tfold $ (1:10:undefined) : (2:3:5:undefined) : (4:undefined) : error "bad"
We have
ghci> bad [1,2*** Exception: bad
but the VIP version would give at least
ghci> bad [1,2,3,4*** Exception: bad / Prelude: undefined
The reason to *not* have the "lazy" patterns in foldTree for primes, as Daniel Fischer discovered back then, is that they give it a space leak. Case in point - http://ideone.com/DLHp2 : ------------- 1M primes: ---- 2M primes: --- 3M: --- ideone #: - no-VIPs: "smart" fold: 1.90s- 4.8MB 4.42s- 4.8MB 7.40s- 4.8MB r3bdL - VIPs: "smart" fold: 1.95s- 4.8MB 4.53s- 4.8MB 7.45s- 4.8MB 4ACpe simple fold: 2.04s- 4.8MB 4.76s- 4.8MB 7.86s- 4.8MB av9XR "lazy" pats: 2.44s-20.1MB 5.70s-21.1MB 9.85s-42.6MB DLHp2 Also, having tfold ((x:xs):t) = x : xs `merge` tfold (pairs t) where pairs ((x:xs):ys:t) = (x : merge xs ys) : pairs t hfold xs = serve . foldTree mergeP . map vip $ xs hfold' xs = serve . foldTree' mergeP . map vip $ xs foldTree f ~(x:xs) = x `f` foldTree f (pairs xs) where pairs ~(x: ~(y:ys)) = f x y : pairs ys foldTree' f (x:xs) = x `f` foldTree' f (pairs xs) where pairs (x: (y:ys)) = f x y : pairs ys and bad = (1:10:error "1") : (2:3:5:error "2") : (4:error "4") : error "bad" bad2 = (1:10:error "1") : (2:3:5:error "2") : (4:error "4") : (5:error "5") : (6:error "6") : (7:error "7") : error "bad2" we get *Main> hfold bad [1,2,3,4*** Exception: bad *Main> hfold' bad [1,2,3,4*** Exception: bad *Main> tfold bad [1,2*** Exception: bad *Main> hfold bad2 [1,2,3,4*** Exception: 4 *Main> hfold' bad2 [1,2,3,4*** Exception: bad2 *Main> tfold bad2 [1,2*** Exception: bad2 so hfold' too appears to be over-eager to-the-right, although still more productive than tfold.
Regards, Heinrich Apfelmus