[Haskell-cafe] V.I.P.s and the associativity of merge'
Will Ness
will_n48 at yahoo.com
Fri Dec 31 03:29:35 CET 2010
Heinrich Apfelmus <apfelmus <at> quantentunnel.de> writes:
>
> 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
>
> --
> http://apfelmus.nfshost.com
>
More information about the Haskell-Cafe
mailing list