Strictness making it worst?
Jorge Adriano
jadrian@mat.uc.pt
Sat, 1 Dec 2001 15:58:47 +0000
> How high can you go with fibac before getting a stack overflow? I'm
> guessing that it's no more than 200000, and that the suspensions have
> the following structure.
100 000 works fine
110 000 stack overflow
>
> fibac (as you described):
>
> c = (+) a b
> d = (+) b c
> e = (+) c d
>
> sfibac:
>
> c = ($!) ((+) a) b
> d = ($!) ((+) b) c
> e = ($!) ((+) c) d
>
> i.e. the ($!) is in the wrong place, and is only making the suspension
> twice as deep. Addition is already strict in both its parameters.
correct, dumb mistake, thanks :)
> > sfibac' n (a,b) | n == 0 = (a,b)
> > | otherwise = sfibac' (n-1) ((,) b $! a+b)
Yeap, got it.
Well, in fact my first aproach was not using pairs:
> sfibac2 :: IntPos -> IntPos -> IntPos -> IntPos
> sfibac2 n a b | n == 0 = a
> | otherwise = sfibac2 (n-1) b $! (a+b)
With pairs I thought I'd write
> dumbfibac :: IntPos -> IntPos -> IntPos -> IntPos
> dumbfibac n a b | n == 0 = a
> | otherwise = dumbfibac (n-1) $! (b,(a+b))
But this would obviously not work because ($!) reduces its 2nd argument to
'head normal form', not 'normal form'.
Anyway IMO it looks way much better then yours sfibac' function :-)
So my question is, is there anyway to force an argument to be reduced to
*normal form*?
a strict fold function defined like,
> sfoldl f a [] = a
> sfoldl f a (x:xs) = (sfoldl f $! (f a x)) xs
would have the same problem as my dumbfibac function.
How do you correctly define a strict fold function?
J.A.