
Daniel Fischer wrote:
> Heinrich Apfelmus wrote:
>>
>> 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 fact, your transformation that fixes the space leaks pretty much
emulates the behavior of the old
data People a = VIP a (People a)  Dorks [a]
structure. This becomes apparent if we put the last two arguments of
spMerge back into a pair:
mergeSP (P a b) ~(P c d) =
let P bc m = spMerge b (P c d) in P (a ++ bc) m
where
spMerge b (P [] d) = P [] (merge b d)
spMerge [email protected](x:xt) [email protected](P (y:yt) d) = case compare x y of
LT > celebrate x (spMerge xt cd )
EQ > celebrate x (spMerge xt (P yt d))
GT > celebrate y (spMerge xs (P yt d))
In particular, forcing dorks (mergeSP ...) also forces the complete
VIP list.
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.
>> 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. [...]
>
> 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?].
Oops, silly me! Mea culpa, of course mergeSP a (mergeSP b (mergeSP c
..))) or any infinite nesting is not going to work with a strict
pattern. >_> <_<
Regards,
Heinrich Apfelmus

http://apfelmus.nfshost.com
_______________________________________________
HaskellCafe mailing list
[email protected]
http://www.haskell.org/mailman/listinfo/haskellcafe

