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