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

[Will Ness]

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
>