Why is it a memoization function?

Question

Could someone please explain to me, why the following code is the memoization:

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

This function use the memoization technique, where intermediate results are saved and later reused. — softshipper, Feb 11 '19 at 20:17
An easier definition would be `let fib :: Int -> Integer; fib = (fib' !!) where fib' = 1 : 1 : zipWith (+) fib' (tail fib')`. — Aadit M Shah, Feb 12 '19 at 08:06
this is a duplicate of [this question](https://stackoverflow.com/q/11466284/849891). due to a technicality, I am unable to close it as a dupe now. — Will Ness, Feb 14 '19 at 10:26
[related answer](https://stackoverflow.com/a/3209189/849891). — Will Ness, Feb 14 '19 at 10:38

score 5 · Accepted Answer · answered Feb 11 '19 at 20:20

5

I assume you're asking how this memoizes fib. fib itself is just an ordinary function. The real magic happens in fib_mem = (map fib [0..] !!), which memoizes fib. This expression is equivalent to saying that fib_mem x = (map fib [0..]) !! x. Let's break this down to see what it's doing:

[0..] is an infinite list starting [0,1,2,3,..] and continuing ad infinitum.
map fib [0..] applies fib to each element of this list, producing a list where each element is the Fibonacci number corresponding to the index of that element, so e.g. 8 is at index 5. This is the importent step; it memoizes fib by applying it to every number, so once the value at a particular index is forced, it does not have to be recalculated.
Then !! is used to get the value back from the list, at the appropriate index.

answered Feb 11 '19 at 20:20

bradrn

8,337
2
22
51

1

I'd say there is also a bit of magic when the "ordinary function" `fib` uses `fib_mem` in its implementation. Or at least, that's part of the technique. – luqui Feb 12 '19 at 05:20
@bradrn `it memoizes fib by applying it to every number` why does it memoizes? – softshipper Feb 12 '19 at 21:13
1

Because once it's applied to one particular number, the compiler knows that that value is at that index in the list, and so can simply look up the value in the list next time. So e.g. if you've requested `fib_mem 5`, the compiler looks up index `5` in the list, which turns out to be the value `fib 5`, which it calculates. Next time you request `fib 5`, the compiler looks up the index `5` in the list again, however the list is now stored not as `[.., fib 5, ...]` but instead as `[..., 8, ...]`, so it can simply look up the previously-calculated value. – bradrn Feb 12 '19 at 21:47

Will Ness · Answer 2 · 2019-02-14T14:45:02.687

0

In case you meant "why is it a memoizing function", the answer is, because it is a CAF (constant applicative form) and has a monomorphic type.

edited Feb 14 '19 at 14:45

answered Feb 14 '19 at 10:24

Will Ness

70,110
9
98
181

Why is it a memoization function?

2 Answers2