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

15 Dec 2008

      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)

This is obviously going to run into problems for large values of `n` so
I introduced a state to keep intermediate results in:

  foo :: Int -> State (UArray Int Int) Int
  foo 0 = return 0
  foo 1 = return 1
  foo 2 = return 2
  foo n = do
      c <- get
      if (c ! n) /= -1
          then return $ c ! n
          else do
              r <- liftM3 (\ a b c -> a + b + c)
                  (foo $ n - 1) (foo $ n - 2) (foo $ n - 3)
              modify (\ s -> s // [(n, r)])
              return r

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)

Then I thought that this still looks pretty deeply recursive, but if I
call the function for increasing values of `n` then I'll simply build up
the state, sort of like doing a for-loop in an imperative language.  I
could then end it with a call to `foo n` and be done.  I replaced `main`
by:

  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

How should I think about this in order to predict this behaviour in the
future?

/M

-- 
Magnus Therning                             (OpenPGP: 0xAB4DFBA4)
magnus＠therning．org             Jabber: magnus＠therning．org
http://therning.org/magnus

Haskell is an even 'redder' pill than Lisp or Scheme.
     -- PaulPotts