[Haskell-cafe] Re: FASTER primes
daniel.is.fischer at web.de
Tue Jan 12 08:00:25 EST 2010
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
> Jan Sparud. Fixing some space leaks without a garbage collector.
"CiteSeerx is momentarily busy, Please try us again, in a few moments.
We apologize for any inconvenience."
:( tried and re-tried.
> 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)
> 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.
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.
> Heinrich Apfelmus
More information about the Haskell-Cafe