Functional Programming in C#: Classic Programming Techniques for Modern Projects

MEMOIZATION

Memoization is a technique to cache values that have been returned previously by function calls. This depends on the parameters and assumes that the function is referentially transparent. There is a distinction between internal and external memoization; both are explained in this chapter.

Referential transparency, or function purity, means that the function returns the same value for every call that uses the same set of parameters, and that the function doesn’t have side effects. If you want to review this topic, see Chapter 3.

You have probably implemented internal memoization or some variation of it in the past. Here’s a simple function:

static int SquareSimple(int x) {

  return x * x;

}

This function is pure, so it’s a candidate for memoization. Before doing so, you should consider these points:

• The algorithm that uses the function should make extensive use of it. There is overhead involved with memoization, and unless the function is going to be called many times, it is more efficient to leave it as it is.
• The parameters that the function is called with are also important, for the same reason. If it is unlikely that the function will be called many times with the same parameter, there will be overhead but no benefit in memoization.
• The function should be sufficiently complex in nature. In reality, simple operations like squaring an integer value are so fast ...