How to use the memoize function in Data.Function.Memoize

Question

After failing to construct my own memoization table I turned to said class and tried using it to speed up a double recursive definition of the Fibonacci sequence:

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

I have tried using the memoize function of the class in several ways, but even the construction below seems about as slow (eating 10 seconds at fib 33):

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = memoize fib (n-1) + memoize fib (n-2)

fib' :: Int -> Int
fib' n = memoize fib n

I have tried distributing memoize in other ways, but the performance doesn't seem to improve. I know there are other ways to have this problem in particular computed more efficiently, but for my original problem I would like to make use of the Memoize package. So my question is, how does one improve performance with the memoize function in this package?

Answer 1

Obviously memoisation is only useful if you do it precisely once, and then call to that multiple times. Whereas in your approach you keep memoising the function over and over again. That's not the idea!

fib' n = memoize fib n

is the right start, yet won't work as desired for a subtle reason: it's not a constant applicative form because it explicitly mentions its argument.

fib' = memoize fib

is correct. Now, for this to actually speed up the fib function you must refer back to the memoised version.

fib n = fib' (n-1) + fib' (n-2)

You see: just adhering to DRY strictly and avoiding as much boilerplate as possible gets you to the correct version!

Answer 2

As other said, the problem is that you are memoizing the top-level calls to the function but you are not using that information to avoid recomputing recursive calls. Let's see how we could make sure that the recursive calls are also cached.

First, we have the obvious import.

import Data.Function.Memoize

And then we are going to describe the call graph of the function fib. To do that, we write a higher order function which uses its argument instead of a recursive call:

fib_rec :: (Int -> Int) -> Int -> Int
fib_rec f 0 = 0
fib_rec f 1 = 1
fib_rec f n = f (n - 1) + f (n - 2)

Now, what we want is an operator which takes such an higher order function and somehow "ties the knot" making sure that the recursive calls are indeed the function we are interested in. We could write fix:

fix :: ((a -> b) -> (a -> b)) -> (a -> b)
fix f = f (fix f)

but then we are back to an inefficient solution: we never memoize anything. The alternative solution is to write something that looks like fix but makes sure that memoization happens all over the place. Let's call it memoized_fix:

memoized_fix :: Memoizable a => ((a -> b) -> (a -> b)) -> (a -> b)
memoized_fix = memoize . go
  where go f = f (memoized_fix f)

And now you have your efficient function fib_mem:

fib_mem :: Int -> Int
fib_mem = memoized_fix fib_rec

You don't even have to write memoized_fix yourself, it's part of the memoize package.

Answer 3

The memoization package won't turn your function magically in a fast version. What will it do is avoid recomputing any old computation:

import Data.Function.Memoize

fib :: Int -> Int
fib 0 = 0
fib 1 = 1
fib n = fib (n-1) + fib (n-2)

fib_mem = memoize fib

val = 40

main = do
    print $ fib val -- slow
    print $ fib val -- slow
    print $ fib_mem val -- slow
    print $ fib_mem val -- fast!

what you need is a way to avoid recomputing any value in the recursive calls. A simple way to do that would be to compute the fibonacci sequence as an infinite list, an take the nth element:

fibs :: [Int]
fibs = 0:1:(zipWith (+) fibs (tail fibs))

fib_mem n = fibs !! n

A more general technique is to carry a Map Int Int and insert the results inside.

fib :: (Map Int Int) -> Int -> (Int, Map Int Int)
-- implementation left as exercise :-)