teaching machines

CS 330 Lecture 32 – Memoization and Folds

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

#include <iostream>
#include <map>

long long fib(int n) {
  static std::map<int, long long> n2fib;

  // Try to find previous result.
  auto match = n2fib.find(n);
  if (match != n2fib.end()) {
    return match->second;
  }

  if (n <= 1) {
    n2fib[n] = 1;
  } else {
    n2fib[n] = fib(n - 2) + fib(n - 1);
  }

  return n2fib[n];
}

int main(int argc, char **argv) {
  std::cout << fib(atoi(argv[1])) << std::endl;
  return 0;
}

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

Comments

Leave a Reply

Your email address will not be published. Required fields are marked *