Parametricity

Thought experiment

Consider the following JavaScript function:

function foo(x) {
  // implementation hidden
}

What can we infer about this function? The short answer is: nothing.

This function looks like takes a single argument, but JavaScript allows a programmer access to additional, undeclared arguments via the arguments object. Even if this function does only consider its declared argument, we don't know what type the argument is expected to be. It could be a number, or an object, or anything in between.

There's no way to know what sort of data structure this function returns, or whether it returns anything at all.

Essentially, we have no way of knowing anything about what this function does, or how we can use it.

Enter types

Using TypeScript, let's tweak this function's declaration and see what happens:

function foo<A>(x: A): A {
  // implementation hidden
}

We've made three small changes:

1. Declare A as a type variable
2. Declare A as the type of the function's input argument
3. Declare A as the type of the function's output value

Now let's see what we can infer about this function.

The function takes exactly one argument of any type we like. That type is represented by the type variable A.

The function returns a value, also of type A. Since the function's input and output types share the same type variable A, its return value has the same type as whatever argument was passed in.

If we call foo(42) with the number 42, then A means number, and the function will return a number.

If we call foo("forty two") with the string forty two, then A means string, and the function will return a string.

The developer writing the implementation can't know anything about what A will be in practice. Is x a number? Maybe it's a string. Perhaps it's an array or an object. It can be any of these, and no matter which it is, the function has to return a value of the same type.

The implementation

It turns out that there's only one possible implementation for a function with this type: identity.

If we ignore bottom cases like null, undefined, and exceptions, the only way to guarantee that we return a value with the same type as the argument is to simply return the argument itself.

function foo<A>(x: A): A {
  return x;
}

This is a property of parametrically polymorphic functions known as parametricity, and is quite useful for API design, library consumption, and generally reasoning about code.

var x: number = foo(42);
console.log(x + ':', typeof x); // 42: number

var y: string = foo("42");
console.log(y + ':', typeof y); // 42: string

Parametricity also applies to more complicated (and more interesting) functions, and allows us to derive useful theorems about them using only their type signatures.

Affordable theorems

Say that r is a function of type:

r : ∀X. X* → X*

In TypeScript, this can be written as:

function r<A>(xs: Array<A>): Array<A> {

An example of a function of this type is reverse:

function reverse<A>(xs: Array<A>): Array<A> {
  var reversed = [];
  for (var i = xs.length - 1; i >= 0; i--) {
    reversed.push(xs[i]);
  }
  return reversed;
}

Say also that a is a total function of type:

a : A → A'

In TypeScript, this can be written for A of number and A' of string as:

function a(x: number): string {

From what we learned in Theorems for free!, we know that:

a* ∘ r_A = r_A' ∘ a*

We can demonstrate this with Node.js using jsverify to generate the function a and sample input xs:

import jsc = require('jsverify');

function arrEq(xs, ys) {
  var eq = xs.length === ys.length;
  for (var i = 0; i < xs.length && eq; i++) { eq = xs[i] === ys[i]; }
  return eq;
}

function map(f) {
  return function (xs) {
    var ys = [];
    for (var i = 0; i < xs.length; i++) { ys.push(f(xs[i])); }
    return ys;
  };
}

function compose(f, g) { return function (x) { return f(g(x)); }; }

jsc.assert(
  jsc.forall('array number', 'number -> string', function (xs, a) {
    return arrEq( compose(reverse, map(a))(xs)
                , compose(map(a), reverse)(xs)
        );
  })
);