teaching machines

CS 330 Lecture 32 – Memoization and Folds

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




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:

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.



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


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