Sharing ES-Discourse discussions, conclusions, and polyfill

[NickGard]

There was a great discussion of a Function.memoize feature in es-discourse.group a while back. I wrote a polyfill for it here.

Notably, the discussion in the es-discourse group revealed that a static method is better suited for this as fn.memo() may be mistaken to be converting fn to a memoized version in place (rather than returning a memoized copy). The polyfill uses WeakRefs to get around the problem of having primitive keys. The polyfill also had an options argument that allowed the user to set a select, hash, and/or compare function to determine the equivalence of arguments.

Guiding principles

The proposal and polyfill were built around these principles:

1. Memoization should be invisible to users. The function that the user desires to memoize should not have to be modified to be memoized (e.g. boxing primitives, or currying functions)
2. The user should not have to manage the cache. It should grow as needed without user intervention.
3. Memoization should be memory-safe. The user should not have to worry about the memoization cache being a memory leak. No arguments, generated keys (defined by a hash function or however), or function results should be strongly referenced. This should extend to the memoization function handling excessively large caches. Whether it completely flushes the cache periodically, or removes the least-used key/values, or does some other memory management, this should be invisible to the users beyond a React-style disclaimer that memoization does not guarantee the function won't be re-run.
4. Users should be able to define equality between sets of arguments. The user may know when the function should return the same result based on arguments, so they may wish to define a way to determine this. This could be a hash function that reduces the set of arguments to a single primitive (probably a string). This could be a compare function that compares arguments pairwise for equality (e.g. given the argument sets a1, a2, a3 and b1, b2, b3, the compare function would be called on [a1, b1], [a2, b2], and [a3, b3]) and returns the cached value if they all return true. This could be a select function that takes the set of arguments as an input and outputs an iterable of values to use as cache keys (similar to how React.memo uses the props passed in to the component).
5. Memoization should be compute-time-safe. The user should not have to worry if the cache-lookup is slower than naively running the memoized function. The implementation should opt to run the function un-memoized (or reduce the cache to a lookup-efficient size) if it detects the lookup is taking longer than the original call.

The polyfill does not fulfill principle 5 (yet).

Syntax

var memoFn = Function.memoize(fn [, options])

fn is the function to be memoized. (It should be a pure function.)

options an object containing any of the following:

• select a function that takes all of the arguments passed to the memoized function as inputs and outputs an iterable that serves as the comparison keys to the memoization cache.
• hash a function that takes either the arguments passed to the memoized function, or the elements in the iterable returned by select if it is also declared, and returns a single value to be used as the comparison key for the memoization cache.
• compare a function that takes each key defined by select and/or hash or the raw arguments as passed to the memoized function (if neither select or hash are declared) and the corresponding key from memoized calls and outputs true if the two keys are equal and false otherwise.

Return memoFn a new function that wraps the passed function and returns the result of a direct call or a saved value as determined by the memoization algorithm.

Examples

function getIn(target, path, fallback) {
  let steps = [...path];
  let value = target;
  while (steps.length) {
    let step = steps.shift();
    if (!(step in value)) return fallback;
    value = value[step];
  }
  return value;
}

const dog = {
  type: 'dog'
  activities: {
    nap: {
      location: 'rug'
    }
  }
};

// with no options
const memoGetIn = Function.memoize(getIn);

// runs unmemoized
memoGetIn(dog, ['activities', 'nap', 'location'], 'bed');

// returns memoized value
memoGetIn(dog, ['activities', 'nap', 'location'], 'bed');

// runs unmemoized because {...dog} is not equal to dog
memoGetIn({...dog}, ['activities', 'nap', 'location'], 'bed');

function hash(target, path, fallback) {
  return `${target.type}__${path.join('_')}__${fallback}`;
}
const memoGetInHashed = Function.memoize(getIn, {hash});

// runs unmemoized
memoGetInHashed(dog, ['activities', 'nap', 'location'], 'bed');

// returns memoized value
memoGetInHashed(dog, ['activities', 'nap', 'location'], 'bed');

// returns memoized value because the hashes are equal
memoGetInHashed({...dog}, ['activities', 'nap', 'location'], 'bed');

function select(target, path, fallback) {
  // ignore everything about the target except the type
  return [target.type, ...path, fallback];
}
const memoGetInSelected = Function.memoize(getIn, {select});

// runs unmemoized
memoGetInSelected(dog, ['activities', 'nap', 'location'], 'bed');

// returns memoized value
memoGetInSelected(dog, ['activities', 'nap', 'location'], 'bed');

// returns memoized value because the selected keys are equal
memoGetInSelected({...dog}, ['activities', 'nap', 'location'], 'bed');

function compare(a, b) {
  return a === b || ( // referentially equal
    typeof a === 'object' && 
    typeof b === 'object' && 
    a.type === b.type // or have same types
  );
}
const memoGetInByType = Function.memoize(getIn, {compare});

// runs unmemoized
memoGetInByType(dog, ['activities', 'nap', 'location'], 'bed');

// returns memoized value
memoGetInByType(dog, ['activities', 'nap', 'location'], 'bed');

// returns memoized value because {...dog}
// compares as equal to dog
memoGetInByType({...dog}, ['activities', 'nap', 'location'], 'bed');