CS 330 Lecture 31 – Composition and Memoization
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/vendor_ruby/rubygems/dependency.rb:315:in `to_specs': Could not find 'coderay' (>= 0) among 94 total gem(s) (Gem::MissingSpecError)
Checked in 'GEM_PATH=/var/www/.local/share/gem/ruby/3.2.0:/var/lib/gems/3.2.0:/usr/local/lib/ruby/gems/3.2.0:/usr/lib/ruby/gems/3.2.0:/usr/lib/x86_64-linux-gnu/ruby/gems/3.2.0:/usr/share/rubygems-integration/3.2.0:/usr/share/rubygems-integration/all:/usr/lib/x86_64-linux-gnu/rubygems-integration/3.2.0:/home/johnch/.gems' , execute `gem env` for more information
from /usr/lib/ruby/vendor_ruby/rubygems/dependency.rb:327:in `to_spec'
from /usr/lib/ruby/vendor_ruby/rubygems/core_ext/kernel_gem.rb:57:in `gem'
from ./coderay:24:in `'