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