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!