Strictness making it worst?
Hi, I've just started messing around with strictness. My goal now is understanding when and how to use it. I began with simple examples like making a strict foldl. When trying to sum a list of 60000 elements with lazy foldl I'd get a stack space overflow, with a strict foldl I was able to sum a list of 1E8 elements :) 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, (+b) $! a)
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) I expect sfibac and fibac work this way: assuming that a+b = c b+c = d c+d = e sfibac: sfibac 4 (a, b) -> sfibac 3 (b, a+b) -> sfibac 2 (a+b, b+(a+b)) -> sfibac 1 (b+(a+b), (a+b)+(b+(a+b))) -> sfibac 0 ((a+b)+(b+(a+b)), (b+(a+b)) + (a+b)+(b+(a+b))) now if I had to evaluate the first element I'd get (a+b)+(b+(a+b)) -> c+(b+c) -> c+d -> e fibac: sfibac 4 (a, b) -> sfibac 3 (b, a+b) -> sfibac 2 (c, b+c) -> sfibac 1 (d, c+d) -> sfibac 0 (e, d+e) I'd expect sfibac to be faster, but what I find even more strange is the stack space overflow in sfibac! why? Greetings, J.A.
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
participants (2)
-
Jorge Adriano -
Tom Pledger