#Closures#Higher-Order Functions

Memoize a Function

Cache a function by its arguments so the same call never computes twice.

By Pratik RaiMedium

Write memoize(fn) returning a function that behaves identically but never recomputes for arguments it has already seen.

The returned function also exposes callCount(), reporting how many times the original actually ran.

Examples

Input:

JSfile.javascript
1const greet = memoize((name, mark) => 'Hi ' + name + mark); 2greet('Ada', '!'); // "Hi Ada!", computed 3greet('Ada', '?'); // "Hi Ada?", computed 4greet('Ada', '!'); // "Hi Ada!", from cache 5greet.callCount();

Output:

2

The second call differs in one argument, so it is a new entry. The third repeats the first exactly and is served from the cache, so the original ran twice.

Constraints

  • Arguments are JSON-serialisable

Notes

  • A cached 0, false or undefined is still a cached value — check whether the key exists, not whether the value is truthy.
  • A stricter version keys on argument identity rather than on a string, which rules out JSON.stringify entirely.

How to solve it

Trading memory for time

Memoisation is a cache keyed by arguments. The interesting parts are not the caching but the two places it quietly goes wrong.

Approach

A Map from a key derived from the arguments to the result.

Implementation

JSfile.javascript
1function memoize(fn) { 2 const cache = new Map(); 3 let callCount = 0; 4 const memoized = function (...args) { 5 const key = JSON.stringify(args); 6 if (cache.has(key)) return cache.get(key); 7 callCount += 1; 8 const value = fn.apply(this, args); 9 cache.set(key, value); 10 return value; 11 }; 12 memoized.callCount = () => callCount; 13 return memoized; 14}

Worth knowing

Check for the key, not the value. if (cache.get(key)) recomputes every cached 0, false, null and undefined. cache.has(key) is the correct test, and the suite checks it with a function that returns 0.

JSON.stringify is a lossy key. Key order changes the string, so {a:1,b:2} and {b:2,a:1} become different entries; functions and undefined vanish; two distinct objects with the same shape collide. A stricter variant keys on argument identity using a tree of Maps, one level per argument, which is exact but never releases what it holds.

Goal: Serve repeat arguments from cache, and report the real call count.

Frequently asked questions

What is memoization?
Caching a function's result against its arguments so the same call never computes twice. It trades memory for time and only works for pure functions, where the same input always gives the same output.
Why check whether the cache has the key rather than the value?
Because 0, false, null, undefined and '' are all legitimate cached results and all falsy. if (cache.get(key)) recomputes every one of them, which is the most common bug in a memoize implementation.
What is wrong with JSON.stringify as a cache key?
Key order changes the string, so two equal objects can produce different keys; functions and undefined disappear; and two genuinely different objects with the same shape collide. It is fine for numbers and strings and unreliable for anything else.
How would you memoize on argument identity instead?
With a tree of Maps, one level per argument, so lookup follows the actual references. That is exact but holds every argument alive forever unless you use WeakMap, which only accepts objects as keys.

Related Challenges

Continue learning with these related challenges

View All
JavaScript

Promisify a Callback Function

Convert a Node-style (error, value) callback API into one that returns a promise.

JavaScript · ES6 — Pratik Rai ·

JavaScript

Run a Function Only Once

A once wrapper: the first call runs, every call after it does nothing.

JavaScript · ES6 — Pratik Rai ·

JavaScript

Infinite Curried Sum

sum(1)(2)(3) with no fixed arity — the running total appears when the result is coerced.

JavaScript · ES6 — Pratik Rai ·