Hi Dmitri, As a reference you might want to take a look at the Project Euler problem #14 and the corresponding dubious entry in the HaskellWiki: http://www.haskell.org/haskellwiki/Euler_problems/11_to_20#Problem_14 .
> *** Question: I wonder how to implement cache for this problem in Haskell? > At the moment, I am not so much interested in the speed of the code, as in > nice implementation. a while ago I wondered about the same question: memoization and more specifically tabulation (DP) in Haskell. After some time I came up with code which does it IMO in a fairly nice way using an array of lazy computations which gives you top-down DP for free at the expense of performance. Another way is to use lazily built tries ala MemoTrie: http://www.haskell.org/haskellwiki/MemoTrie . Specific implementation: > import Data.Array > import Data.MemoTrie I write the collatz function using open recursion in order to separate the recursive function from the memo scheme. > type Gen a = a -> a > type Fix a = Gen a -> a > > collatzGen :: Gen (Integer -> Integer) > collatzGen c 1 = 1 > collatzGen c n | even n = 1 + c (div n 2) > | otherwise = 1 + c (3*n + 1) We can use plain old Data.Function.fix to get the usual stupid recursive function or use our custom fixpoint combinators. |fixtab| for example uses an array to cache the result in the given range. When the argument is outside of the range the normal recursive scheme is applied. > fixtab :: Ix i => (i, i) -> Fix (i -> r) > fixtab b f = f' > where a = listArray b [ f f' i | i <- range b ] > f' i = if inRange b i then a!i else f f' i Another option is to use the MemoTrie package where we can write a fixpoint combinator like this: > fixmemo :: HasTrie i => Fix (i -> r) > fixmemo f = let m = memo (f m); in m And of course the final collatz function: > collatz :: Integer -> Integer > collatz = fixtab (1,1000000) collatzGen Cheers, Steven _______________________________________________ Haskell-Cafe mailing list Haskell-Cafe@haskell.org http://www.haskell.org/mailman/listinfo/haskell-cafe