January 24, 2015

Consider the following JavaScript function:

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.

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

We’ve made three small changes:

- Declare
`A`

as a type variable - Declare
`A`

as the type of the function’s input argument - 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.

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.

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.

Say that `r`

is a function of type:

*r : ∀X. X* → X**

In TypeScript, this can be written as:

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:

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