How to use the memoize function in Data.Function.Memoize
fibonacci, haskell, memoization
Solution
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!
Problem
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?