On Mon, Dec 15, 2008 at 11:33 PM, Lemmih <lem...@gmail.com> wrote: > 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)
Ah, OK that does explain it. I understand your solution, but AFAICS it's geared towards limited recursion in a sense. What if I want to use memoization to speed up something like this foo :: Int -> Int foo 0 = 0 foo 1 = 1 foo 2 = 2 foo n = sum [foo i | i <- [0..n - 1]] That is, where each value depends on _all_ preceding values. AFAIK list access is linear, is there a type that is a more suitable state for this changed problem? I realise this particular function can be written using scanl: foo :: Int -> Int foo n = ackList !! n where ackList = 0:1:2:(drop 2 $ scanl1 (+) ackList) but I guess it's not always that easy to construct a solution based on scanl. Cheers, M -- Magnus Therning (OpenPGP: 0xAB4DFBA4) magnus@therning.org Jabber: magnus@therning.org http://therning.org/magnus identi.ca|twitter: magthe
_______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe