Am Donnerstag 14 Januar 2010 08:25:48 schrieb Will Ness:
Daniel Fischer
writes: Am Mittwoch 13 Januar 2010 10:43:42 schrieb Heinrich Apfelmus:
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.
I think that is responsible. At least that's how I understand the core:
mergeSP (a,b) ~(c,d) = (a ++ bc, merge b' d) where (bc, b') = spMerge b c spMerge ...
That is equivalent to
first (a++) . second (`merge`d) $ spMerge b c
and Daniel's fix is equivalent to
first (a++) $ spMerge b c d
Now, when compiler sees the first variant, it probably treats spMerge as opaque. I.e. although in reality spMerge only contributes to the first "channel" while it is progressively instantiated, and (`merge`d) will only be called upon when spMerge's final clause is reached, that is (most likely) not known to the compiler at this stage. When looking at just the first expression itself, it has to assume that spMerge may contribute to both channels (parts of a pair) while working, and so can't know _when_ /d/ will get called upon to contribute to the data, as it is consumed finally at access.
So /d/ is gotten hold of prematurely, _before_ going into spMerge.
No, the problem is that d itself is gotten hold of too late, it is accessed only indirectly via the pair, so we keep an unnecessary reference to c via d.
The second variant passes the responsibility for actually accessing its inputs to spMerge itself, and _it_ is clear about needing /d/ only in the very end.
The second variant is clear about not needing the _pair_ anymore once spMerge is entered. Thus d doesn't reference c anymore.
Just a theory. :)
Does that make sense?