teaching machines

CS 330 Lecture 31 – Composition and Memoization

April 20, 2016 by . Filed under cs330, lectures, spring 2016.




We’ve seen that we can create functions several ways:

  1. by defining a named function
  2. by partially applying parameters to get a new function expecting only the remaining parameters
  3. by defining unnamed lambdas
  4. by composing a gauntlet of functions together

This is in Haskell. We just touched upon the last of these at the end of last lecture. Let’s look at one more example: absmax, which computes the maximum distance from 0 of all the elements in the list. We’ll piece together maximum and abs.

Let’s use composition to create a few more frankenfunctions. We’ll also introduce type synonyms, which come up in your homework. In our case, we’ll just give a more meaningful name to a rectangle’s bounds:

type Rectangle = (Int, Int, Int, Int)
  1. find the smallest area from a list of rectangles
  2. find the number of squares in a list of rectangles

What’s the type signature of the . operator? It’s implementation?

Which of these function-generating mechanisms can we do in Java?

We’ll next look at a clever little mechanism for speeding up a function whose behavior is determined solely by the parameters. (This precondition is easily achieved in a language where “variables” are immutable.) Inside the function, we keep a lookup table between the parameters and the function’s return value. On the first calls to this function, the lookup table will be empty, and we will have to do the real work to compute the return value. But if later calls give us parameters that we’ve seen before, we can simply retrieve the value from the lookup table. This technique is called memoization. One of the homework problems involves memoization. We’ll implement the yawn Fibonacci sequence using memoization. First we’ll write a C++ implementation to show how’s it done, but then we’ll look at a Haskell implementation that is made almost automatically with the help of the Memoize module.

Next time we’ll dive into the fold pattern.



import Data.Function.Memoize
import Data.List

absmax :: [Int] -> Int
-- absmax l = maximum (map abs l)
absmax = (maximum . map abs)

type Rectangle = (Int, Int, Int, Int)
area :: Rectangle -> Int
area (l, b, r, t) = (r - l) * (t - b)

smallestArea :: [Rectangle] -> Int
-- smallestArea rectangles = minimum (map area rectangles)
smallestArea = minimum . map area

-- Slow slow slow!
fib' :: Integer -> Integer
fib' n
  | n <= 1 = 1
  | otherwise = fib' (n - 1) + fib' (n - 2)

-- Fast fast fast!
fib :: Integer -> Integer
fib = memoize helper
    helper n
      | n <= 1 = 1
      | otherwise = fib (n - 1) + fib (n - 2)


/usr/lib/ruby/2.7.0/rubygems/dependency.rb:311:in `to_specs': Could not find 'coderay' (>= 0) among 56 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/.gem/ruby/2.7.0:/var/lib/gems/2.7.0:/usr/lib/ruby/gems/2.7.0:/usr/share/rubygems-integration/2.7.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/2.7.0:/home/johnch/.gems', execute `gem env` for more information
	from /usr/lib/ruby/2.7.0/rubygems/dependency.rb:323:in `to_spec'
	from /usr/lib/ruby/2.7.0/rubygems/core_ext/kernel_gem.rb:62:in `gem'
	from ./coderay:24:in `