0

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:

Ilya Silvestrov
  • 347
  • 3
  • 7
  • `!!` is `O(n)` and not like in other languages `O(1)`. I'm not sure that's the only problem though. – user1984 Nov 26 '21 at 02:15
  • @user1984, yes indeed it's sub-optimal. But `fibMemoDirect` also uses `!!` and works ~200 times faster. – Ilya Silvestrov Nov 26 '21 at 02:17
  • To make sure they differ asymptotically and the difference isn't just some constant, I suggest to run the code for (30 * 5) and (30 * 10) and see how the times change. – user1984 Nov 26 '21 at 02:20
  • `fibMemoDirect 3000` completes in 0.13 seconds. `memo fib 3000` never completes. – Ilya Silvestrov Nov 26 '21 at 02:23
  • 2
    Your fib function is directly recursive and doesn't use its `f` argument. So you could as well run it without `fix` and you'd get the same result in the same time. That's why replacing `fix` with `memo` makes no difference. – sepp2k Nov 26 '21 at 02:26
  • @sepp2k, oh yes! That's such an embarrassment! – Ilya Silvestrov Nov 26 '21 at 02:43

1 Answers1

4

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.

Louis Wasserman
  • 191,574
  • 25
  • 345
  • 413