Natural Transformations

A fascinating aspect of category theory is its multiscale description of modern mathematics both at structure level and theory level. For instance,

  • a `group`_ is a category (with only one object • and a set of invertible morphisms g : • → •) while all groups form the objects of the Grp category (with group morphisms as morphisms)

  • a `partial order`_ is a category (with arrows from lower to greater elements) while all partial orders form the objects of the Ord category (with increasing functions as morphisms)

In both examples above, one might check that morphisms actually coincide with functors from one structure (group/partial order) to an other structure (each a category).

Naturality

Natural transformations are a cornerstone of category theory. As functors describe relationships between categories, natural transformations describe relationships beween functors.

Given two functors F and G from C to C’, a natural transformation T : F → G is defined by a collection T[a] : F(a) -> G(a) such that for all ϕ : a -> b, one has:

G.fmap(ϕ) @ T[a] = T[b] @ F.fmap(ϕ)

To characterize natural transformations, one thus usually says that the following diagram commutes:

       T[a]
 F(a) -----> G(a)
  |           |
ϕ |           | ϕ
  v           V
 F(b) -----> G(b)
       T[b]

Functor Categories

With the above definitions, one may define a category of functors from C to C’ and usually denoted [C, C’] (or C' ** C in exponent format) given two categories C and C’. Its objects are functors from C to C’, and morphisms are natural transformations between such functors.

If follows that functors from Type to Type form a special category, called the category of type endofunctors.

Examples

A group representation is a functor ρ : G → Vect mapping the group’s unique object • to a vector space V, and mapping every group element g : • → • to a linear isomorphism ρ(g) : V → V. A morphism of representations T : ρ → ρ’ is a natural transformation from ρ to ρ’.

Natural transformations play an important role in functional programming, as we shall see further in the manual. As a first example, consider the Tree functor defined above. Then there is a natural transformation flatten: Tree -> List such that for every type a,

  • flatten[a] maps Tree(a)(x, []) to [x] (leaves)

  • flatten[a] maps Tree(a)(x, subtrees) to [x, *flatten[a](t) for t in subtrees] (recursion)

The fact that actual implementations do not depend on the type parameter a (only type signatures do) is a sign of naturality.

In many other examples, explicit knowledge of natural maps T[a] : F(G(a)) -> G(F(a)) (commutation relation) between two functors is very useful. Assume for instance that F = List and G = Async (mapping type a to a promise for a value x: a). Then a natural transformation

  • parallel : List @ Async -> Async @ List

ought to be defined, by waiting for all asynchronous calls to return their values before gathering them in a list. Such commutation relations give rise to monad transformers.