» CS 330 Lecture 32 – Memoization and Folds

CS 330 Lecture 32 – Memoization and Folds

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

Agenda

what ?s
memoization in C++
the fold pattern

TODO

Funfun before Monday! The thingies have been pretty unreliable lately. If you are on Windows, I really recommend getting >=4 GB USB drive and installing Linux on it. The last assignment will require JRuby again. (You can run this stuff on Windows too, but you can’t run the tester there.)

Note

Last time we closed with some Haskell memoize magic. Let’s see if we can recreate that magic in C++ with the fib function.

We’ll then discuss the pattern of patterns: fold (aka reduce, inject). We start by implementing sum', length', and prod'. From there we have enough instances of the pattern to abstract it into our fold' function.

The fold pattern requires two parameters from us: the base-case identity value that gets returned when the folded collection is empty, and the “glom” function that mixes an element into the accumulated result.

With fold defined, we re-express a number of functions using this pattern:

any', which accepts a list of Bool and reports whether any element is true
all', which accepts a list of Bool and reports whether all elements are true
map'
filter'
maximum'
contains'

This leads to the key takeaway from this part of the course: when your functions can accept functions as parameters, redundant patterns that we see all over our code can be abstracted out. All that remains is for us to fill the holes of that abstraction. Lambdas allow us to fill those holes without a lot of fanfare.

Code

fib.cpp

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

fold.hs

sum' [] = 0
sum' (first:rest) = first + sum' rest

prod' [] = 1
prod' (first:rest) = first * prod' rest

length' [] = 0
length' (first:rest) = 1 + length' rest

fold' _ identity [] = identity
fold' glom identity (first:rest) = glom first (fold' glom identity rest)

sum'' = fold' (+) 0
prod'' = fold' (*) 1
length'' = fold' (\item accum -> accum + 1) 0

any' :: [Bool] -> Bool
any' = fold' (||) False

all' = fold' (&&) True