Magnus Therning wrote:
This behaviour by Haskell seems to go against my intuition, I'm sure I just need an update of my intuition ;-)
I wanted to improve on the following little example code:
foo :: Int -> Int foo 0 = 0 foo 1 = 1 foo 2 = 2 foo n = foo (n - 1) + foo (n - 2) + foo (n - 3)
Two more ideas: How about -- "loop" keeping the last three elements of the sequence -- O(n) per call, constant memory foo' :: Int -> Int foo' n = go n 0 1 2 where go 0 a _ _ = a go n a b c = go (n - 1) b c (a + b + c) or -- analogue of the folklore fibonacci definition: -- fibs = 0 : 1 : zipWith (+) fibs (tail fibs) foos :: [Int] foos = 0 : 1 : 2 : zipWith3 (\a b c -> a + b + c) foos (tail foos) (tail (tail foos)) [snip]
Then I added a convenience function and called it like this:
createArray :: Int -> UArray Int Int createArray n = array (0, n) (zip [0..n] (repeat (-1)))
main = do (n:_) <- liftM (map read) getArgs print $ evalState (foo n) (createArray n)
[snip]
main = do (n:_) <- liftM (map read) getArgs print $ evalState (mapM_ foo [0..n] >> foo n) (createArray n)
Then I started profiling and found out that the latter version both uses more memory and makes far more calls to `foo`. That's not what I expected! (I suspect there's something about laziness I'm missing.)
Anyway, I ran it with `n=35` and got
foo n : 202,048 bytes , foo entries 100 mapM_ foo [0..n] >> foo n : 236,312 , foo entries 135 + 1
The number of function calls is to be expected: to evaluate foo n for the first time, you need to call foo (n-1), foo (n-2) and foo (n-3), making 4 calls per evaluated value. 36*4 = 144 is pretty close to 135. (The "missing" 9 calls correspond to foo 0, foo 1 and foo 2) The difference of 35 can be explained in the same way: the first version makes 35 fewer explicit calls to 'foo'. Bertram