Strictness making it worst?

[Tom Pledger]

Jorge Adriano writes:
 :
 | Then I thought I'd mess with the fibonnaci function. 
 | I began with:
 | 
 | > fibac                     :: IntPos -> (IntPos,IntPos) -> (IntPos,IntPos)
 | > fibac n (a,b) 
 | >               | n == 0    = (a,b)
 | >               | otherwise = fibac (n-1) (b,a+b)
 | 
 | 
 | Then I tried:
 | 
 | > sfibac                     :: IntPos -> (IntPos,IntPos) -> (IntPos,IntPos)
 | > sfibac n (a,b) 
 | >                | n == 0    = (a,b)
 | >                | otherwise = sfibac (n-1)   (b, (a+) $! b)

(amended as per your second message)

 | I tried both functions with ghc 5.00.1
 | The strict version was not only slower, but I'd get stack overflows for 
 | numbers that worked with the 1st version!! (like 100000)

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.

    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.

This version moves the ($!) from (+)'s second argument to (,)'s second
argument, to ensure that the addition is done as soon as the pair is
constructed, i.e. in time for the pattern match in the very next
recursive call.  Hence it runs in O(1) stack space (but still O(n)
space overall, due to the exponentially large numbers involved).

> sfibac' n (a,b) | n == 0    = (a,b)
>                 | otherwise = sfibac' (n-1) ((,) b $! a+b)

Regards,
Tom