Hi Dimitri,
When asking "how to implement cache in Haskell" I was hopping that there exists some solution without using Data.Array, more "functional" approach, if I may say so ...
Steven's second solution is purely functional. It uses so-called tries to cache results instead of mutable arrays. Here is an alternative definition of Steven's `fixmemo` function: fixmemo :: HasTrie a => ((a -> b) -> (a -> b)) -> (a -> b) fixmemo f = fix (memo . f) It uses the standard fixpoint combinator Data.Function.fix :: (a -> a) -> a and has a similar (but more restrictive) type. In order to understand Steven's solution you need to know how to define recursive functions using a fixpoint combinator. For example, you can define the Fibonacci function as follows: fibonacci :: Int -> Integer fibonacci = fix fib fib :: (Int -> Integer) -> (Int -> Integer) fib fib 0 = 0 fib fib 1 = 1 fib fib n = fib (n-1) + fib (n-2) Note how the first argument `fib` of the function `fib` shadows the name of the global function `fib`. The advantage of this complicated definition is that you get a memoized version of the `fibonacci` function simply by using `fixmemo` instead of `fix`: memoFib :: Int -> Integer memoFib = fixmemo fib This definition avoids to recompute the same recursive calls over and over again in is therefore much faster than the original version. That said, memoization helps to solve your original problem only if you reuse the cache for different top-level calls of the Collatz length function. According to the Collatz conjecture no argument appears again when computing the Collatz length of a number (otherwise the computation would not terminate). Ryan's solution achieves reuse of the cache by defining it at the top level and you can do the same with tries. For the `fib` example it would look like this: fibCache :: Int :->: Integer fibCache = trie (fib cachedFib) cachedFib :: Int -> Integer cachedFib = untrie fibCache Now even independent calls to `cachedFib` reuse previously computed results. In my experiments, caching did not pay off, even for computing the maximum Collatz length of a given range. Without caching it took less than 5 seconds to compute the maximum Collatz length of all numbers between 1 and 1000000. With caching, it took 30 seconds. Cheers, Sebastian