## 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.