Magnus Therning magnus at therning.org
Mon Dec 15 18:08:40 EST 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

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

-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 197 bytes
Desc: OpenPGP digital signature