TypeScript: a typed memoize wrapper

Cache the results of a pure function with a generic higher-order function and count how often the body runs.

TypeScript

let bodyRuns = 0;

function memoize<T extends string | number, R>(fn: (arg: T) => R): (arg: T) => R {
  const cache = new Map<T, R>();
  return (arg: T): R => {
    if (cache.has(arg)) {
      return cache.get(arg) as R;
    }
    const value = fn(arg);
    cache.set(arg, value);
    return value;
  };
}

const fib: (n: number) => number = memoize((n: number): number => {
  bodyRuns++;
  return n < 2 ? n : fib(n - 1) + fib(n - 2);
});

console.log("fib(25) = " + fib(25) + ", body ran " + bodyRuns + " times");
const before = bodyRuns;
fib(25);
console.log("repeat call: " + (bodyRuns - before) + " more runs");
const mark = bodyRuns;
console.log("fib(30) = " + fib(30) + ", " + (bodyRuns - mark) + " more runs");

Output

fib(25) = 75025, body ran 26 times
repeat call: 0 more runs
fib(30) = 832040, 5 more runs

Explanation

Memoization stores the result of a call so that a repeated call with the same argument is answered from a cache. It trades memory for time, and it turns a recursive function with overlapping subproblems, such as Fibonacci, from exponential into linear time.

memoize is generic: T is the argument type and R is the result type, so the wrapper keeps the exact signature of the function it wraps. The cache uses has instead of testing for undefined, so a function that legitimately returns undefined is cached correctly. The counter records how many times the real function body runs.

Explore the dry run

Guided walkthroughReady

1let bodyRuns = 0;

3function memoize<T extends string | number, R>(fn: (arg: T) => R): (arg: T) => R {

4 const cache = new Map<T, R>();

5 return (arg: T): R => {

6 if (cache.has(arg)) {

7 return cache.get(arg) as R;

8 }

9 const value = fn(arg);

10 cache.set(arg, value);

11 return value;

12 };

13}

15const fib: (n: number) => number = memoize((n: number): number => {

16 bodyRuns++;

17 return n < 2 ? n : fib(n - 1) + fib(n - 2);

18});

20console.log("fib(25) = " + fib(25) + ", body ran " + bodyRuns + " times");

21const before = bodyRuns;

22fib(25);

23console.log("repeat call: " + (bodyRuns - before) + " more runs");

24const mark = bodyRuns;

25console.log("fib(30) = " + fib(30) + ", " + (bodyRuns - mark) + " more runs");

Follow the example

Start to inspect the source, values, and output. These prepared steps explain the published sample; grouped loop steps describe multiple iterations.

View the complete dry-run table

Prepared trace of the published program. Some rows group repeated iterations.
What happens	State after step	Output so far
A generic wrapper: it accepts any function from T to R and returns a function of the same type.	`—`	—
A cached argument is answered without running the function again.	`—`	—
This counts the real computations. Each n from 0 to 25 runs once.	`—`	—
26 distinct arguments (0 to 25), 26 runs.	`bodyRuns = 26`	fib(25) = 75025, body ran 26 times
The second call is a cache hit.	`bodyRuns = 26`	fib(25) = 75025, body ran 26 times repeat call: 0 more runs
Only the five new arguments 26 to 30 need computing.	`bodyRuns = 26`	fib(25) = 75025, body ran 26 times repeat call: 0 more runs fib(30) = 832040, 5 more runs

Cost and common mistakes

Without caching Θ(φⁿ) time; with caching Θ(n) time and Θ(n) space.

Only memoize pure functions. If a result depends on time, randomness, or outside state, the cache returns stale values.
The cache grows without bound. Long-running programs need an eviction policy such as LRU.
Object arguments are compared by reference in a Map, so two equal objects are two different keys.

Try it yourself

How many body runs does fib(10) need on a fresh cache?

Reveal answer and reasoning

11 runs, one for each n from 0 to 10.

TypeScript: a typed memoize wrapper

Explanation

Follow the example

Cost and common mistakes

Try it yourself

Further reading