Generalized recursion doesn't work for Haskell memoization

Question

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

!! is O(n) and not like in other languages O(1). I'm not sure that's the only problem though. — user1984
– user1984, Commented Nov 26, 2021 at 2:15
@user1984, yes indeed it's sub-optimal. But fibMemoDirect also uses !! and works ~200 times faster. — Ilya Silvestrov
– Ilya Silvestrov, Commented Nov 26, 2021 at 2: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
– user1984, Commented Nov 26, 2021 at 2:20
fibMemoDirect 3000 completes in 0.13 seconds. memo fib 3000 never completes. — Ilya Silvestrov
– Ilya Silvestrov, Commented Nov 26, 2021 at 2:23
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
– sepp2k, Commented Nov 26, 2021 at 2:26

Louis Wasserman · Accepted Answer · 2021-11-26 02:32:44Z

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.

answered Nov 26, 2021 at 2:32

Louis Wasserman

200k26 gold badges367 silver badges437 bronze badges

Sign up to request clarification or add additional context in comments.

Collectives™ on Stack Overflow

Generalized recursion doesn't work for Haskell memoization

1 Answer 1

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related