[Haskell-cafe] Re: FASTER primes

[Will Ness]

Daniel Fischer <daniel.is.fischer <at> web.de> 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.

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.

Just a theory. :) 

Does that make sense?