Memoisation

Trading memory for time

Memoisation stores the result of a function call keyed by its arguments and returns the stored result on repeated calls. It is only correct for pure functions, since an impure function may legitimately return something different next time. It shines for expensive computations with repeated inputs and for recursive problems with overlapping subproblems (dynamic programming). Watch out for unbounded cache growth, keys for object arguments (reference versus content equality) and caching that costs more than recomputing. Python ships functools.lru_cache and functools.cache; React offers useMemo and memo for rendering.

A generic memoise helper

Single primitive argument keeps the key simple.

function memoise<A extends string | number, R>(fn: (a: A) => R): (a: A) => R {
  const cache = new Map<A, R>();
  return (a: A) => {
    if (cache.has(a)) return cache.get(a) as R;
    const result = fn(a);
    cache.set(a, result);
    return result;
  };
}

// Naive Fibonacci makes an exponential number of calls; memoised it is linear
const fib: (n: number) => number = memoise((n: number) =>
  n < 2 ? n : fib(n - 1) + fib(n - 2),
);

A lookup table on the wall

Instead of redoing long multiplication each time, a student writes answers on a table and checks it first. That only works because 7 x 8 never changes its answer.

त्वरित जाँच: Why must a memoised function be pure?

• Otherwise the cached result may be wrong for later calls with the same arguments
• Because caches only accept numbers
• Because pure functions cannot be called twice
• Because memoisation removes the function