TypeScript: a typed memoize wrapper

Before you start

TypeScript generics and Map.

Cache the results of a pure function with a generic higher-order function and count how often the body runs.
Predict the sample output and explain the state changes.
Complete the practice task and check the boundary cases.

The concept

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.

Code example

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

Example details

Follow the code

Open the walkthrough to inspect the example one step at a time.

Show guided walkthrough

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

Behind the scenes

How TypeScript processes this code

TypeScript checks types and emits JavaScript. Type annotations are removed before execution.

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.