# [Haskell-cafe] V.I.P.s and the associativity of merge'

Will Ness will_n48 at yahoo.com
Sat Jan 1 12:29:15 CET 2011

```Heinrich Apfelmus <apfelmus <at> quantentunnel.de> writes:

>
> Will Ness wrote:
> > Heinrich Apfelmus writes:
> >> Here an example where the VIP merge would give a different result
> >>
> >>      bad = tfold \$ (1:10:undefined) : (2:3:5:undefined) : (4: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 :
> >
> > [...]
> >
> >    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
> >
> > [...]
> >
> > so hfold' too appears to be over-eager to-the-right, although still more
> > productive than tfold.
>
> Ah, the lazy patterns in  foldTree  are a different issue, sorry for my
>
> While I still don't understand the trade-off that turns the lazy
> patterns into a space leak, there is no harm in allowing  foldTree  to
> see the complete spine of the list. What we do want to forbid is looking
> at the elements of that list too early.

This turns out to be too optimistic a demand on data, in general.

> In other words, the example
>
>              (1:10:undefined) : (2:3:5:undefined) : (4:undefined)
>              : repeat (error "bad" : undefined)
>
> i.e. the previously unknown tail is replaced with an infinite list of
> undefined elements. This example can properly distinguish between the
> not-so-correct  tfold  and proper VIP implementations (or other
> implementations that don't do unnecessary comparisons).
>

will have to think this over, but in the mean time, they *both* turn out to be
*completely* and utterly *wrong* :) in a general case (although probably for
different reasons).

Here's where:

*Main> mapM_ print \$ take 5 \$ map (take 10)
[concatMap (replicate 3) [n,n+1..]|n<-[1..]]
[1,1,1,2,2,2,3,3,3,4]
[2,2,2,3,3,3,4,4,4,5]
[3,3,3,4,4,4,5,5,5,6]
[4,4,4,5,5,5,6,6,6,7]
[5,5,5,6,6,6,7,7,7,8]

*Main> take 20 \$ hfold [concatMap (replicate 3) [n,n+1..]|n<-[1..]]
[1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7]

*Main> take 20 \$ tfold [concatMap (replicate 3) [n,n+1..]|n<-[1..]]
[1,1,1,2,2,2,3,3,3,4,4,4,5,5,5,6,6,6,7,7]

when it should'a been

[1,1,1,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,4,4]

Cheers,

:)

> Regards,
> Heinrich Apfelmus
>
> --
> http://apfelmus.nfshost.com
>

```