Home > Software engineering >  Generalized recursion doesn't work for Haskell memoization
Generalized recursion doesn't work for Haskell memoization

Time:11-26

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:

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.

  • Related