[Haskell-cafe] Re: FASTER primes

[Daniel Fischer]

Am Dienstag 12 Januar 2010 11:30:07 schrieb Heinrich Apfelmus:
> Tricky stuff. It is known that pairs/records are prone to unwanted
> retention, see for example the recent thread
>
>   http://thread.gmane.org/gmane.comp.lang.haskell.cafe/66903/focus=67871
>
> or
>
>   Jan Sparud. Fixing some space leaks without a garbage collector.
>   http://citeseer.ist.psu.edu/240848.html

"CiteSeerx is momentarily busy, Please try us again, in a few moments.
We apologize for any inconvenience."

:( tried and re-tried.

Took http://bert.md.chalmers.se/pub/cs-reports/papers/sparud/spaceleak-
fix.ps.gz finally

>
> 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 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. In other words,
>
>   mergeSP :: Integral a => People a -> People a -> People a
>   mergeSP (P a b) (P c d) = P (a ++ bc) (merge b' d)
>       where
>         P bc b' = spMerge b c
>         spMerge [] ys = P [] ys
>         spMerge xs [] = P [] xs
>         spMerge xs@(x:xt) ys@(y:yt) = case compare x y of
>                 LT -> celebrate x (spMerge xt ys)
>                 EQ -> celebrate x (spMerge xt yt)
>                 GT -> celebrate y (spMerge xs yt)
>
> should work fine and do away with the memory issue because the pair is
> now deconstructed immediately.

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

>
> Hm, a strict second argument might however mean that the tree produced
> by  tfold  is demanded too early.
>

>
>
> Regards,
> Heinrich Apfelmus
>
> --
> http://apfelmus.nfshost.com