# Parametricity

January 24, 2015

## Thought experiment

Consider the following JavaScript function:

``````function foo(x) {
// implementation hidden
}``````

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
}``````

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

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 special 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 {``

a* ∘ rA = rA' ∘ 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)
);
})
);``````