Daniel Fischer wrote:
Heinrich Apfelmus wrote:
It is exactly because these troubles that I'm advocating the original VIP data structure that buries the dorks (that name is awesome :D) deep inside the structure. :)
In fact, your transformation that fixes the space leaks pretty much emulates the behavior of the old data People a = VIP a (People a) | Dorks [a] structure. This becomes apparent if we put the last two arguments of spMerge back into a pair: mergeSP (P a b) ~(P c d) = let P bc m = spMerge b (P c d) in P (a ++ bc) m where spMerge b (P [] d) = P [] (merge b d) spMerge xs@(x:xt) cd@(P (y:yt) d) = case compare x y of LT -> celebrate x (spMerge xt cd ) EQ -> celebrate x (spMerge xt (P yt d)) GT -> celebrate y (spMerge xs (P yt d)) In particular, forcing dorks (mergeSP ...) also forces the complete VIP list. I wonder whether it's really the liveness of pair in mergeSP (a,b) pair = let sm = spMerge b (fst pair) in (a ++ fst sm, merge (snd sm) (snd pair)) that is responsible for the space leak, for chances are that Sparud's technique applies and pair is properly disposed of. Rather, it could be that we need the stronger property that forcing the second component will evaluate the first to NF.
In any case, it appears to me that the lazy pattern match in mergeSP is actually unnecessary! This is because mergeSP returns a pair constructor immediately, so infinite nesting works even when the second argument is demanded. [...]
No, <<loop>>. For the reason you stated below. In
tfold f (a:b:c:xs) = (a `f` (b `f` c)) `f` smartfold f xs
, it must compute smartfold f xs too early to match it against P c d. The compiler can't see that smartfold mergeSP always returns a P [well, it might return _|_, mightn't it?].
Oops, silly me! Mea culpa, of course mergeSP a (mergeSP b (mergeSP c ..))) or any infinite nesting is not going to work with a strict pattern. >_> <_< Regards, Heinrich Apfelmus -- http://apfelmus.nfshost.com