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

[Heinrich Apfelmus]

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"
>> 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 : 
>  
> [...]
>  
>    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.

Leon Smith wrote:
> At a glance, it appears to have to do with the irrefutable patterns
> that treefold uses. At the moment,  it's not obvious to me how your
> example could be made to "work" without either giving up the ability
> to work correctly on finite cases, or giving up the tree and going
> back to foldr merge'.  ;-)
> 
> [...]
> 
> Also,  is there other examples that could distinguish a VIP
> implementation that works on finite cases,   and a no-VIP
> implementation?   Is it possible to have a VIP example that works on
> finite cases and is maximally lazy in this example?

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. 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).


Regards,
Heinrich Apfelmus

--
http://apfelmus.nfshost.com