2008/12/16 Magnus Therning <mag...@therning.org>: > 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?
Immutable arrays are duplicated every time you write to them. Making lots of small updates is going to be /very/ expensive. You have the right idea, though. Saving intermediate results is the right thing to do but arrays aren't the right way to do it. In this case, a lazy list will perform much better. > ack n = ackList !! n > where ackList = 0:1:2:zipWith3 (\a b c -> a+b+c) ackList (drop 1 ackList) > (drop 2 ackList) -- Cheers, Lemmih _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe
