# teaching machines

## CS 330 Lecture 36 – Memoization

April 30, 2014 by . Filed under cs330, lectures, spring 2014.

### Agenda

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

### Program This

• Write a Haskell function that returns the nth 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