Memoization with recursion

Question

I am trying to understand Haskell realization of memoization , but I don't get how it works:

memoized_fib :: Int -> Integer
memoized_fib = (map fib [0..] !!)
    where fib 0 = 0
              fib 1 = 1
              fib n = memoized_fib(n - 2) + memoized_fib(n - 1)

First of all I even don't understand why 'map'-function get three parameters (function - fib, list [0..], and ||), but not two how it must do.

Updated:

I have tried to rewrite the code, but get the different result:

f' :: (Int -> Int) -> Int -> Int
f' mf 0 = 0
f' mf 1 = 1
f' mf n = mf(n - 2) + mf(n - 1)

f'_list :: [Int]
f'_list = map (f' faster_f') [0..]

faster_f' :: Int -> Int
faster_f' n = f'_list !! n

Why? Is the any error in my reasoning?

they could've put some extra parenthesis there to make it a bit more obvious (map fib [0..] !!) == ((map fib [0..]) !!) — soulcheck
– soulcheck, Commented Feb 23, 2012 at 9:48
The different result in your update is because of Int overflow. Use Integer instead; apart from that it seems right to me at first glance. — yatima2975
– yatima2975, Commented Feb 23, 2012 at 11:58

Tikhon Jelvis · Accepted Answer · 2012-02-23 09:45:55Z

9

First: Haskell supports operator sections. So (+ 2) is equal to \ x -> x + 2. This means the expression with map is equal to \ x -> map fib [0..] !! x.

Secondly, how this works: this is taking advantage of Haskell's call-by-need evaluation strategy (its laziness).

Initially, the list which results from the map is not evaluated. Then, when you need to get to some particular index, all the elements up to that point get evaluated. However, once an element is evaluated, it does not get evaluated again (as long as you're referring to the same element). This is what gives you memoization.

Basically, Haskell's lazy evaluation strategy involves memoizing forced values. This memoized fib function just relies on that behavior.

Here "forcing" a value means evaluating a deferred expression called a thunk. So the list is basically initially stored as a "promise" of a list, and forcing it turns that "promise" into an actual value, and a "promise" for more values. The "promises" are just thunks, but I hope calling it a promise makes more sense.

I'm simplifying a bit, but this should clarify how the actual memoization works.

edited Feb 23, 2012 at 9:45

answered Feb 23, 2012 at 9:40

Tikhon Jelvis

68.3k19 gold badges183 silver badges217 bronze badges

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

4 Comments

ceth Over a year ago

Thank. I have tried to rewrite my code with new knowledge, but get the different result (updated section in my question). Why? As I see this pieces of code must be equal.

David Ren Over a year ago

Why, for instance, in function calls memoized_fib(n - 2) and memoized_fib(n - 1), the list map fib [0..] refer to the same list in memory?

Noughtmare Over a year ago

The expression with map is critically not equal to \x -> map fib [0..] !! x. That would destroy the sharing! (Unless you compile with GHC's optimizations which is smart enough to restore the sharing.) Instead, it is equal to (!!) (map fib [0..]).

Noughtmare Over a year ago

(Or if you do want to show a fully applied version, I'd suggest let fibs = map fib [0..] in \x -> fibs !! x.)

Fred Foo · Accepted Answer · 2012-02-23 09:38:39Z

2

map does not take three parameters here.

(map fib [0..] !!)

partially applies (slices) the function (!!) with map fib [0..], a list, as its first (left-hand) argument.

answered Feb 23, 2012 at 9:38

Fred Foo

365k80 gold badges765 silver badges852 bronze badges

Comments

Useless · Accepted Answer · 2012-02-23 10:06:31Z

2

Maybe it's clearer written it as:

memoized_fib n = (map fib [0..]) !! n

so it's just taking the nth element from the list, and the list is evaluated lazily.

This operator section stuff is exactly the same as normal partial application, but for infix operators. In fact, if we write the same form with a regular function instead of the !! infix operator, see how it looks:

import Data.List (genericIndex)

memoized_fib :: Int -> Integer
memoized_fib = genericIndex (map fib [0..])
    where fib 0 = 0
              fib 1 = 1
              fib n = memoized_fib(n - 2) + memoized_fib(n - 1)

answered Feb 23, 2012 at 10:06

Useless

68.5k6 gold badges100 silver badges143 bronze badges

2 Comments

ceth Over a year ago

Here is two version of function (pastebin.com/sA6ib2kp). Why the first one run faster, but second one - slower?

Tom Ellis Over a year ago

Because the list is shared in the first version but not the second version.

Collectives™ on Stack Overflow

Memoization with recursion

3 Answers 3

4 Comments

Comments

2 Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

2 Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related