[Haskell-cafe] Re: FASTER primes

[Daniel Fischer]

Am Donnerstag 14 Januar 2010 08:25:48 schrieb 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.

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?
>