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