TypeScript: a typed memoize wrapper
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.
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");