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! is not, in general, equal to

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. - a set

Categories show up all over the place.