» CS 330 Lecture 31 – Composition and Memoization

CS 330 Lecture 31 – Composition and Memoization

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

Agenda

what ?s
composition in Haskell
memoization in C++
memoization in Haskell

TODO

On Wednesday night at 7 PM, I am giving a talk on Madeup at the Acoustic Cafe as part of the Ask a Scientist series. Attend and provide some proof of attendance (a sketch of me with one of the presented models, a soiled napkin, a receipt, a selfie with me, etc.) on Friday for two extra credit participation points.

Note

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

by defining a named function
by partially applying parameters to get a new function expecting only the remaining parameters
by defining unnamed lambdas
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)

find the smallest area from a list of rectangles
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.

Code

today.hs

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
  where
    helper n
      | n <= 1 = 1
      | otherwise = fib (n - 1) + fib (n - 2)

Composer.java

/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 `'