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

[Will Ness]

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) :
> >>                    error "bad"
> > 
> > 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 
> bad choice of example.
> 
> 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 
> should read
> 
>      bad = tfold $
>              (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
>