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
_______________________________________________
Haskell-Cafe mailing list
Haskell-Cafe@haskell.org
http://www.haskell.org/mailman/listinfo/haskell-cafe
