Implement memoize

The question

It looks like a two-line question and then the follow-ups arrive:

1. What if the function returns undefined?
2. Should f(2) and f("2") share a cache entry?
3. What about object arguments, and when does the cache get released?

The solution

The cache is created inside memoize, so each memoized function gets its own and two of them can never interfere.

function memoize(func) {
  // A Map per memoized function, so two of them never share a cache.
  const cache = new Map();

  return function (...args) {
    // The type is part of the key, so 2 and "2" cannot collide.
    const key = JSON.stringify(args.map((arg) => [typeof arg, arg]));

    // has(), not a truthiness check: a cached undefined is still a cache hit.
    if (cache.has(key)) return cache.get(key);

    const result = func.apply(this, args);
    cache.set(key, result);
    return result;
  };
}

How it works

The type is part of the key. Mapping each argument to [typeof arg, arg] before stringifying keeps the number 2 and the string "2" apart. Use cache.has(key) rather than a truthiness check, or a function that legitimately returns undefined gets recomputed forever. The cache is created inside memoize, so two memoized functions can’t interfere, and func.apply(this, args) keeps the receiver so memoizing a method still works.

The tests it has to pass

This is the part most explanations leave out. "It works" is not a claim you can check by reading. These are the 6 cases Practice Pad runs against your solution, and the implementation above passes all of them.

let calls = 0;
const square = memoize((value) => {
  calls += 1;
  return value * value;
});
expectEqual([square(4), square(4), calls], [16, 16, 1]);

let calls = 0;
const shout = memoize((value) => {
  calls += 1;
  return value.toUpperCase();
});
expectEqual([shout("hi"), shout("hi"), shout("bye"), calls], ["HI", "HI", "BYE", 2]);

let calls = 0;
const describe = memoize((value) => {
  calls += 1;
  return typeof value + ":" + String(value);
});
expectEqual([describe(2), describe("2"), calls], ["number:2", "string:2", 2]);

let calls = 0;
const double = memoize((value) => {
  calls += 1;
  return value * 2;
});
expectEqual([double(1), double(2), double(1), calls], [2, 4, 2, 2]);

let leftCalls = 0;
let rightCalls = 0;
const left = memoize((value) => {
  leftCalls += 1;
  return value + "-L";
});
const right = memoize((value) => {
  rightCalls += 1;
  return value + "-R";
});
expectEqual([left("k"), right("k"), left("k"), leftCalls, rightCalls], ["k-L", "k-R", "k-L", 1, 1]);

let calls = 0;
const alwaysUndefined = memoize(() => {
  calls += 1;
  return undefined;
});
alwaysUndefined(1);
alwaysUndefined(1);
expectEqual(calls, 1);

Edge cases to watch out for

Using a falsy check for the cache hit

if (cache[key]) return cache[key] misses every result that’s 0, "", false, null or undefined, so those are recomputed forever. Map.has() is the correct test.

Building the key with String(args) or join

String([2]) and String(["2"]) are both "2", so the two calls collide. So do f(1, 2) and f("1,2"). Include the type, or use a delimiter that can’t appear in the values.

Declaring the cache outside memoize

A module-level cache is shared by every memoized function, so two of them overwrite each other's entries. The first hard test creates two and checks they stay independent.

Assuming JSON.stringify handles every argument

It can’t key on object identity, throws on circular references, and drops functions. For object arguments a WeakMap keyed on the object itself is usually the better structure, and saying so is worth mentioning.

Follow up questions

See all 24 questions