## 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.

### 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.

• I’ve never studied Hoare logic under that name; from a brief glance at the wikipedia article, it looks like static analysis. I did plan to talk about the Curry-Howard isomorphism.

It doesn’t make much sense to define “homomorphism” all by itself; I defined “monoidal homomorphism” before I used it.

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.

• Oops! I forgot to pass `g` through `str_to_str`! (But `f` is fine). I’ll fix that, thanks!

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)).

• Wow, good catch. With first-order contracts, it doesn’t matter, but here it certainly does. Thanks again! (This is actually the first time I’ve tried programming with contracts…)

• Heard the word before but never tried to get into it. Now it’s crystal clear. Thanks for that, too

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)?