Memoize Higher-Order Function
Memoization caches function results keyed by arguments so repeat calls return in O(1). This snippet covers the canonical single-arg memoize, a multi-arg version that handles object identity via a `Map` chain, and an LRU-bounded variant that prevents unbounded cache growth. Use it for pure functions whose work dwarfs the lookup cost (parsing, layout calc, recursive DP).
458 views
7
function memoize(fn) {
const cache = new Map();
return function memoized(arg) {
if (cache.has(arg)) return cache.get(arg);
const result = fn.call(this, arg);
cache.set(arg, result);
return result;
};
}
let calls = 0;
const fib = memoize((n) => {
calls += 1;
return n < 2 ? n : fib(n - 1) + fib(n - 2);
});
console.log(fib(20)); // 6765
console.log('calls:', calls); // 21 (each n computed once via the wrapper)
console.log(fib(20)); // 6765 (cache hit, no extra work)
console.log('calls:', calls); // 21When the function takes one primitive argument (number, string, boolean), a plain Map is the cleanest cache: O(1) lookup, structural equality on keys, and no JSON.stringify overhead. Memoizing a recursive function flips a naive O(2^n) Fibonacci to O(n) by sharing sub-results, which is why DP problems get a speed-up just by adding this wrapper. The body must recurse through fib (the memoized binding) rather than a self-referencing inner name, otherwise the recursion bypasses the cache. Use this version any time the input space is small and primitive.
function memoizeMulti(fn) {
const root = new Map();
return function memoized(...args) {
let node = root;
for (let i = 0; i < args.length; i++) {
if (!node.has(args[i])) node.set(args[i], new Map());
node = node.get(args[i]);
}
if (node.has('__value__')) return node.get('__value__');
const result = fn.apply(this, args);
node.set('__value__', result);
return result;
};
}
let workCount = 0;
const sum = memoizeMulti((a, b, c) => {
workCount += 1;
return a + b + c;
});
console.log(sum(1, 2, 3)); // 6
console.log(sum(1, 2, 3)); // 6 (hit)
console.log(sum(1, 2, 4)); // 7 (miss, only last branch differs)
console.log('runs:', workCount); // 2Stringifying arguments (JSON.stringify(args)) is the lazy way to support many arguments, but it breaks for objects (key order), Functions, BigInts, and circular refs. A trie of nested Maps sidesteps all of that: each argument carves one layer deeper, and the leaf holds the cached value under a sentinel key. This also gives correct identity semantics for object arguments (two distinct {} are different keys, just like in a normal Map). The trade-off is memory: every distinct prefix of arguments allocates a Map, so for cheap functions the overhead can outweigh the benefit.
function memoizeLRU(fn, max = 100) {
const cache = new Map();
return function memoized(arg) {
if (cache.has(arg)) {
const cached = cache.get(arg);
cache.delete(arg);
cache.set(arg, cached);
return cached;
}
const result = fn.call(this, arg);
cache.set(arg, result);
if (cache.size > max) {
const oldestKey = cache.keys().next().value;
cache.delete(oldestKey);
}
return result;
};
}
const slow = memoizeLRU((n) => n * n, 3);
slow(1); slow(2); slow(3); slow(4); // evicts 1
console.log(slow(1)); // recomputed: 1
console.log(slow(4)); // cached: 16The unbounded Map cache leaks memory in long-running services where the input space is huge or unbounded (per-request URLs, user IDs, file paths). Promoting the just-accessed key to the end of the Map's insertion order on every hit, then evicting keys().next().value when the size exceeds max, gives you a correct LRU in eight extra lines. JavaScript Map preserves insertion order specifically so this pattern works without extra data structures. Tune max based on the size of the cached values and the working-set size of your traffic.