[Haskell-cafe] Re: FASTER primes

[Heinrich Apfelmus]

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