[Haskell-cafe] Re: FASTER primes
Heinrich Apfelmus
apfelmus at quantentunnel.de
Wed Jan 13 04:43:42 EST 2010
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 xs@(x:xt) cd@(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
More information about the Haskell-Cafe
mailing list