CS 330 Lecture 36 – Memoization

Agenda

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

TODO

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

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *