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