[Haskell-cafe] V.I.P.s and the associativity of merge'
will_n48 at yahoo.com
Sat Jan 1 12:29:15 CET 2011
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
> > Fischer discovered back then, is that they give it a space leak. Case in
> > 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
*Main> mapM_ print $ take 5 $ map (take 10)
[concatMap (replicate 3) [n,n+1..]|n<-[1..]]
*Main> take 20 $ hfold [concatMap (replicate 3) [n,n+1..]|n<-[1..]]
*Main> take 20 $ tfold [concatMap (replicate 3) [n,n+1..]|n<-[1..]]
when it should'a been
> Heinrich Apfelmus
More information about the Haskell-Cafe