Short version: Memoization is per-input-set caching of a function’s outputs.
Long version:
Imagine I have a function that’s expensive, used a lot, and referentially transparent. Maybe a function getPrime(n) that gives me the nth prime number.
Remember that the output of a referentially transparent function depends only on its inputs. If my function is expensive, and I expect to call it a bunch of times with the same input, it might be helpful for me to remember the result the first time I call it with that input, and simply return that result on subsequent calls, rather than doing the expensive calculation again.
That remembering is memoization.
As usual, an example will help. Happily, I can easily steal a good one from underscore.js instead of writing my own.
_.memoize = function(func, hasher) {
var memoize = function(key) {
var cache = memoize.cache;
var address = '' + (hasher ? hasher.apply(this, arguments) : key);
if (!_.has(cache, address)) cache[address] = func.apply(this, arguments);
return cache[address];
};
memoize.cache = {};
return memoize;
};
Does this make sense?
_.memoize is the function declared. It’s a higher-order function, taking a function func and a hash function hasher, and returning a new function, the memoized version of func.
_.memoize returns a wrapper around func with a cache and some extra logic added. The wrapper is the memoized version of func.
When the memoized function is called, it first uses the hash function on the arguments to create an address. The address is a single value that’s used as a cache key used for those arguments.
The function then checks whether there’s an entry in the cache for that address. If there isn’t, it runs the original function and adds the result to the cache. If there is, it skips the running of the original function, because it already has the result.
Finally, the function returns the cache entry for the address.
A simple object {} is attached to the memoized function and used as its cache. It’s defined as a property of the function, rather than inside it, so it persists across calls to that function.
And with this, I can memoize getPrime(n):
let getPrimeMemoized = _.memoize(getPrime);
One last note: Think about what happens if I memoize a function that has side effects. The original function will only be called the first time I call the memoized version. So the side effects won’t happen on subsequent calls.
