After reading several sources, I came up with the following memo
function for memoization in Haskell with "generalized recursion." But it doesn't work. Why?!
fib f 0 = 1
fib f 1 = 1
fib f n = fib f (n - 1) fib f (n - 2)
memo f n = fList !! n
where fList = map (f (fList !!)) [0..]
Recursive run w/o memoization
λ> fix fib 30
1346269
(1.65 secs, 962,135,992 bytes)
It takes the same time as a "memoized" version:
λ> memo fib 30
1346269
(1.62 secs, 962,141,192 bytes)
However, the following works:
fibMemoDirect n = fibList !! n
where fibList = map fib [0..]
fib 0 = 1
fib 1 = 1
fib n = fibList !! (n - 1) fibList !! (n - 2)
λ> fibMemoDirect 30
1346269
(0.01 secs, 93,728 bytes)
Why doesn't memo fib
above work as fast as fibMemoDirect
given that both use CAF?
Sources:
- Haskell Wiki
- Edward Kmett's Stackoverflow answer
CodePudding user response:
You've almost gotten it, but your third line needs to be
fib f n = f (n-1) f (n-2)
...or else you're not even using f
and just writing a normal, recursive, exponential Fibonacci function.