Memoization and injections

A higher-order contract takes a function and returns a wrapped function obeying some input/output contract. If we want to trade memory for time, we can cache the results of a function so we don’t have to recompute them; a side-effect is that the result is guaranteed to be functional: it will always return the same value for a given input. For simplicity, assume the function takes a string as input.

// First-order contract
var func = function (f) {
  if (typeof f !== 'function') {
    throw new TypeError('Expected a function.');
  }
  return f;
};

// Higher-order contract
var memoize = function (f) {
  func(f);
  var memo = {};
  return function (s) {
    str(s);
    // The '$' prefix avoids issues with
    // magic properties like __proto__.
    var key = '$' + s;
    if (key in memo) {
      return memo[key];
    }
    return memo[key] = f(s);
  };
};

A variant of this technique lets us write a contract for injections—that is, functions where two inputs can never give the same output. Here, for simplicity, assume the function f outputs a string.

// Another higher-order contract
var injection = function (f) {
  func(f);
  var memo = {};
  return function (s) {
    var key = '$' + str(f(s));
    if (key in memo && s !== memo[key]) {
      throw new TypeError('Violated ' +
          'injection contract!');
    } else {
      memo[key] = s;
    }
    return f(s);
  };
};

Notice that f may not actually be an injection; we’ll only get an error if the wrapper realizes it’s not an injection.

There is a category whose objects are contracts and whose morphisms are injections between them. It is a very different category from the one whose objects are contracts and whose morphisms are functions between them. For example, suppose we have two contracts A, B that each allow only a finite set of values to satisfy them—say a and b elements, respectively. Then there are b^a functions between them, but only {b \choose a} = \frac{b!}{(b-a)!a!} injections because injections aren’t allowed to repeat outputs.

Advertisements

One Comment to “Memoization and injections”

  1. Giorgio Mossa asked about taking advantage of caching in the second example on the G+ page.

Leave a Reply

Please log in using one of these methods to post your comment:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: