Chapter 13

2.7 練習問題



  1. Define a higher-order function (or a function object) \code{memoize} in your favorite language. This function takes a pure function \code{f} as an argument and returns a function that behaves almost exactly like \code{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.
  2. Try to memoize a function from your standard library that you normally
    use to produce random numbers. Does it work?
  3. 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?
  4. Which of these C++ functions are pure? Try to memoize them and observe what happens when you call them multiple times: memoized and not.
  5. The factorial function from the example in the text.
  6. std::getchar()
  7. bool f() {
      std::cout << "Hello!" << std::endl;
      return true;
  8. int f(int x) {
      static int y = 0;
      y += x;
      return y;
  9. How many different functions are there from \code{Bool} to \code{Bool}? Can you implement them all?
  10. Draw a picture of a category whose only objects are the types \code{Void}, \code{()} (unit), and \code{Bool}; with arrows corresponding to all possible functions between these types. Label the arrows with the names of the functions.