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"
The reason to *not* have the "lazy" patterns in foldTree for primes, as
Fischer discovered back then, is that they give it a space leak. Case in
Daniel point -
[...]
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