Natural transformations

We’ve seen stack homomorphisms and monoid homomorphisms. These are homomorphisms between implementations of an interface.

There’s also a general notion of a homomorphism between two arbitrary functors, which is a variant of the hom functor.

var natural = function (f, g) {
  func(f); func(g);
  return function (x, y) {
    y = y || x;
    func(x); func(y);
    return hom([f(x)], g(y));
  };
};

Just as we used hom when defining the interface of a monoid, we can use natural when defining the interface of a monad:

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

var monadOf = function (m, n) {
  n = n || m;
  func(m); func(n);
  return function (intr) {
    return function (t) {
      return makeInterface({
        '*': natural(compose(m, m), n)(t),
        1: natural(id, n)(t)
      })(intr);
    };
  };
};

Given categories C and D and functors F:C \to D and G:C \to D, a natural transformation n: F \Rightarrow G assigns to every object c of C a morphism n(c):F(c) \to G(c) such that for every morphism m:c_1 \to c_2 in C,

n(c_2) \circ F(m) = G(m) \circ n(c_1).

The flatten function is a natural transformation from compose(arrOf, arrOf) to arrOf. It takes a doubly-nested array to a singly-nested array, no matter what the type of the elements in the array. Also, it doesn’t matter if you first map a function over the list of lists and then flatten:

flatten(int)(arrOf(arrOf(function (x) { return x+1; }))([[1, 2], [3]]))

or if you flatten first and then map:

arrOf(function (x) { return x+1; }))(flatten(int)([[1, 2], [3]]).

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: