Functors

Here’s a contract that checks if the input is an array of natural numbers.

var arrOfNat32 = function (a) {
  arr(a);
  return a.map(nat32);
};

First it checks to see that a is an array; next it applies nat32 to each element of the array.

Here’s a higher-order contract that takes a contract c and returns a contract that checks if the input is an array of values passing c.

var arrOf = function (c) {
  func(c);
  return function (a) {
    arr(a);
    return a.map(c);
  };
};

Now we can write things like

var arrOfNat32 = arrOf(nat32);
var arrOfStr_to_str = arrOf(hom(str, str));

Note that the function arrOf is a currying of the map method; JavaScript defines Function.prototype.bind for currying, so we could also have written it as

var arrOf = hom([func], hom([arr], id))
    (Function.prototype.bind.bind([].map));

The function arrOf acts both on contracts and on the functions between them. For example, the function atoi has the type signature nat32 -> str, while arrOf(atoi) has the type signature arrOf(nat32) -> arrOf(str).

A functor F from a category C to a category D

  • assigns to every object c in C an object F(c) in D
  • assigns to every morphism m:c -> c' in C a morphism F(m):F(c) -> F(c') in D

such that composition and identities are preserved—that is,

  • F(function (x) { return m(n(x)); })
    = function (x) { return F(m)(F(n)(x)); }
    , and
  • F(id_c) = id_Fc.

The function arrOf is a functor from the category of contracts and functions between them to itself. It maps each contract c to a new contract arrOf(c), and each function f:c -> c' to a new function arrOf(f):arrOf(c) -> arrOf(c').

Optimizing compilers use properties of functors like arrOf or map to make code faster. If a is an array, then

a.map(f).map(g) = a.map(function (x) { return g(f(x)); })

The right-hand version only iterates over the array once, saving a lot of time; this technique is called “map fusion”.

Advertisements

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: