Takashi's Notes

Types and Functions

3 min read

Types and Functions

Prev: Category: The Essence of Composition Next: Categories Great and Small

Prev: Category: The Essence of Composition Next: Categories Great and Small

Exercises

  1. Define a higher-order function (or a function object) memoize in your favorite language. This function takes a pure function f as an argument and returns a function that behaves almost exactly like f, except that it only calls the original function once for every argument, stores the result internally, and subsequently returns this stored result every time it’s called with the same argument. You can tell the memoized function from the original by watching its performance. For instance, try to memoize a function that takes a long time to evaluate. You’ll have to wait for the result the first time you call it, but on subsequent calls, with the same argument, you should get the result immediately.
use std::collections::HashMap;
                              
struct Memoize<A, B> {
    f: Box<dyn Fn(A) -> B>,
    cache: HashMap<A, B>,
}                                         
                
impl<A: Eq + std::hash::Hash + Clone, B: Clone> Memoize<A, B> {                    
    fn new(f: impl Fn(A) -> B + 'static) -> Self {
        Self { f: Box::new(f), cache: HashMap::new() }
    }
 
    fn call(&mut self, arg: A) -> B {
        if let Some(v) = self.cache.get(&arg) {
            return v.clone();
        }
        let result = (self.f)(arg.clone());
        self.cache.insert(arg, result.clone());
        result
    }
}
  1. Try to memoize a function from your standard library that you normally use to produce random numbers. Does it work?

It “works” in that it returns output. But it breaks the contract of randomness, so that part breaks.

  1. Most random number generators can be initialized with a seed. Implement a function that takes a seed, calls the random number generator with that seed, and returns the result. Memoize that function. Does it work?

This would not break the contract of randomness, so yes, this does work.

  1. Which of these C++ functions are pure? Try to memoize them and observe what happens when you call them multiple times: memoized and not. The candidates are the factorial function from the example in the text, std::getchar(), and these two functions:
bool f() {
    std::cout << "Hello!" << std::endl;
    return true;
}
int f(int x) {
    static int y = 0;
    y += x;
    return y;
}

Neither of these are pure, so memoizing them breaks their behavior. If you memoize the first, you don’t run the print call, on a rerun, so you would break that behavior. For the second, the static call would be frozen at whatever the first argument provided before memoization is, even though it should change the static int.

  1. How many different functions are there from Bool to Bool? Can you implement them all?

4:

true → true false → true true → false false → false

  1. Draw a picture of a category whose only objects are the types Void, () (unit), and Bool; with arrows corresponding to all possible functions between these types. Label the arrows with the names of the functions.
      absurd              absurd
Void ---------> ()  Void ---------> Bool 
                                         
()  ----------> ()   (unit)
()  ----------> Bool (true, false -- 2 functions)                                 

Bool ---------> ()   (unit -- 1 function, discards input)
Bool ---------> Bool (id, not, const_true, const_false -- 4 functions)

Graph View

Backlinks