Some more categories

Recall that a category consists of

  • a collection of objects, and
  • for any pair of objects A, B, a set of morphisms between them (if f is a morphism from A to B, we write f:A -> B)

such that

  • every object A has an identity morphism id_A:A -> A;
  • we can compose morphisms f, g if the target object of f matches the source object of g;
  • composition is associative; and
  • composing with the identity gives back the same morphism.

Here are some categories with just a single object.

  • The category with one object str and morphisms generated by applying makeConcat to strings:
    var makeConcat = function (s) {
      str(s);
      return function (t) {
        return str(t) + s;
      };
    };
    

    The identity morphism is makeConcat('').

  • The category with one object nat32 and morphisms generated by applying makeAdd to natural numbers:
    var makeAdd = function (s) {
      nat32(s);
      return function (t) {
        return nat32(t) + s;
      };
    };
    

    The identity morphism is makeAdd(0).

  • The category with one object nat32 and morphisms generated by applying makeMultiply to natural numbers:
    var makeMultiply = function (s) {
      nat32(s);
      return function (t) {
        return nat32(t) * s;
      };
    };
    

    The identity morphism is makeMultiply(1).

  • The category with one object
    // A higher-order contract
    var str_to_str = function (f) {
      func(f);
      return function (s) {
        return str(f(str(s)));
      };
    };
    

    that insists that f:str -> str, and morphisms given by applying makeCompose to functions from str to str:

    var makeCompose = function (f) {
      f = str_to_str(f);
      return function (g) {
        g = str_to_str(g);
        return function (s) {
          return g(f(s));
        };
      };
    };
    

    The identity is makeCompose(function (s) { return s; }).

A monoid is a category with one object. Any time you’re adding or multiplying values, you’re using a one-object category. Note that it’s not true for exponentiation! a^{(b^c)} is not, in general, equal to (a^b)^c.

Here are three functions that share an interesting property:

// Tells whether the number of 1 bits
// in the binary expansion of n is
// even or odd.
var parity = function (n) {
  nat32(n);
  var p = 0;
  while (n > 0) {
    p = p ^ (n & 1);
    n = n >> 1;
  }
  return nat32(p);
};

// Returns the length of the string.
var length = function (s) {
  str(s);
  return nat32(s.length);
};

// Applies g to every element of an array.
var map = function (g) {
  func(g);
  return function (a) {
    arr(a);
    var result = [];
    for (var i = 0; i < a.length; ++i) {
      result[i] = g(a[i]);
    }
    return result;
  };
};
  • parity(n ^ m) = parity(n) ^ parity(m)
  • length(s + t) = length(s) + length(t)
  • for all arrays a,
    map(function (x) { return g(f(x)); })(a);
    

    is the same as

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

A monoid homomorphism between monoids M and N is a function f that preserves composition and identity. That is, it maps the morphisms of M to the morphisms of N in such a way that given two morphisms m and m' of M, composing first and then applying f is the same as applying f to each and then composing the results in N:

f(m m') = f(m) f(m'), and
f(id_M) = id_N.

Here are some other useful categories.

  • The category whose objects are real numbers (the numbers themselves, not contracts), and where a single morphism exists between m and n if m <= n. Composition of morphisms is transitivity: for all m, n, p, we have m <= n <= p implies m <= p. The identity morphism for a number is reflexivity: for all m, m <= m.
  • The category whose objects are monoids and whose morphisms are monoid homomorphisms.
  • The category whose objects are natural numbers (the numbers themselves) and whose morphisms from m to n are n-by-m matrices of integers. Composition is matrix multiplication.
  • A directed multigraph consists of
    • a set N of nodes,
    • a set E of edges,
    • a function source:E -> N, and
    • a function target:E -> N.

    This definition allows for parallel edges and self-directed edges.

    Given any such directed multigraph, there is a category whose objects are the nodes and whose morphisms are the paths. (If there’s an edge from A to B and from B to C, there’s not necessarily an edge from A to C, but there is a path from A to C.) The identity morphism for an object is the “path of length zero” that starts and ends in the same place.

Categories show up all over the place.

Advertisements

12 Comments to “Some more categories”

  1. Just the ticket for learning type-safe javascript. I was going to ask if you could write about Hoare logic and coalgebraic specification. I’d never thought of either a category of contract nor that an exponential couldn’t be a monoid.
    I think you might have used homomorphism before defining it.
    Great fun.

  2. I hope this isn’t too much off topic but are there mathematicians who don’t accept that, in principle, if you can prove, you can program? Voevodsky’s Univalent Foundations paper suggests to me that he thinks all new mathematical constructions will be cast in the form of proofs in a theorem prover like Coq building on the trusted base of proofs.

    • I think the disbelief goes the other way: contructivists say unless you can program, you can’t prove. In constructive logic, “true” means “I have a proof” and false means “I have a counterexample” and there’s no principle of the excluded middle since I may not have evidence either way. In the other camp there are mathematicians, like Gödel, who say things like “unprovable but true”; I think these are generally called “Platonists”.

  3. Thanks for that. I’ve never come across a computer programming Platonist. FWIW The Stanford Encyclopedia of Philosophy cllaims there is no consensual description of what mathematical Platonism means.

    Notwithstanding Godel, I can’t see any reason why every proof should not be programmed and stuck in the reusable library.

    So back to practical categories 🙂

  4. Hi. Won’t makeCompose() return a function that will return the composition g(f(…)) regardless of what f() does at runtime? Shouldn’t the str_to_str() call go before the innermost return? Nice Topic for a blog btw.

  5. Umm. That you didn’t state before so i wouldn’t have noticed. No, i mean that str_to_str(f) returns a function requivalent to f but making sure that the contract holds. I don’t have my thinking cap at hand right now but to me it seems you’d want to return g(str_to_str(f)(s)).

  6. In the law for map, shouldn’t the second expression be parenthesized like this:

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

    In other words, apply map(g) to the result of applying map(f) to x (instead of applying map(g) to map(f), which should violate the contract)?

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: