[Haskell-cafe] How to think about this? (profiling)

[Bertram Felgenhauer]

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