CODEWITHSUNDEEP
haskell
ceth
ceth

Reputation: 45295

Memoization with recursion

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?

Upvotes: 9

Views: 714

Answers (3)

Useless
Useless

Reputation: 67733

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)

Upvotes: 2

Tikhon Jelvis
Tikhon Jelvis

Reputation: 68152

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.

Upvotes: 9

Fred Foo
Fred Foo

Reputation: 363567

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.

Upvotes: 2

Related Questions