## CS 330 Lecture 36 – Memoization

### Agenda

- what ?s
- program this
- the benefits of no side-effects
- memoization in Haskell
- memoization in Ruby

### TODO

- Read about tool selection and the lack of silver bullets: http://blog.awe.sm/2012/12/10/how-to-choose-the-right-tool-for-the-job-awe-sms-language-journey and http://frankchimero.com/blog/no-new-tools.
- Read on laziness in D: http://dlang.org/lazy-evaluation.html.
- Go to CERCA (Ojibwe Ballroom, 3rd floor Davies) and talk to some student researchers.
- Pick one or two or three. 1/4 sheet.

### Program This

- Write a Haskell function that returns the
`n`

th Fibonacci number. Recall that:`fib(0) = 0`

`fib(1) = 1`

`fib(2) = fib(1) + fib(0)`

`fib(3) = fib(2) + fib(1)`

`fib(4) = fib(3) + fib(2)`

- etc.

- You are starting at the upper-left corner of a grid (let’s call it 0, 0) and want to make your way to the bottom right (let’s call it x, y). How many possible paths are there for you to take? Don’t be inefficient—each step you take must be right or down, to bring you closer to the destination. Write a Haskell function to compute the number of paths.The problem is easier if you work in reverse. Start at x, y. If you are at your destination (0, 0), you found a valid path. If you’ve gone off the grid, that’s not a path. Otherwise, you have two choices: come in from the left or come in from above.

### Code

#### fibs.hs

```
import Data.Function.Memoize
fib :: Int -> Int
fib n
| n == 0 = 0
| n == 1 || n == 2 = 1
| otherwise = fib (n - 1) + fib (n - 2)
fastfib :: Int -> Int
fastfib = memoize fibHelper
where
fibHelper :: Int -> Int
fibHelper n
| n == 0 = 0
| n == 1 || n == 2 = 1
| otherwise = fastfib (n - 1) + fastfib (n - 2)
nroutes :: Int -> Int -> Int
nroutes = memoize2 nroutesHelper
where
nroutesHelper :: Int -> Int -> Int
nroutesHelper x y
| x == 0 && y == 0 = 1
| x < 0 || y < 0 = 0
| otherwise = nroutes (x - 1) y + nroutes x (y - 1)
```

#### memoize.rb

```
#!/usr/bin/env ruby
def fib n
if n <= 1
n
else
fib(n - 2) + fib(n - 1)
end
end
def memoize symbol_to_f
cache = Hash.new
f = method(symbol_to_f)
l = lambda do |*params|
# Check cache for f(n) first. Try to reuse earlier result.
if not cache.has_key? params
cache[params] = f.call(*params)
end
cache[params]
end
Object.send(:define_method, symbol_to_f, l)
l
end
memoize :fib
(1..20).each do |n|
puts fib(n)
end
puts fib(30)
```

### Haiku

It’s hard to do both

“Be fruitful and multiply”

Unless you memoize

“Be fruitful and multiply”

Unless you memoize

## Leave a Reply