Natural transformations

We know that Functors map between categories.

Consider:

• two categories $C, D$
• two object $a, b \in C$
• a functor $F : C \to D$

Our objects $a$ and $b$ will map to $F(a)$ and $F(b)$ and the morphism $f := a \to b$ will map to $F(f) := F(a) \to F(b)$.

If we think in programming terms, viewing functors as some kind of containers, we transform the elements inside the container without doing anything to the actual container.

forall a b. (a -> b) -> (F a -> F b)

What if we transform the container instead, leaving the elements untouched?

Consider another functor $G : C \to D$. This transformation should look like this:

forall a. F a -> G a

We get to the idea of natural transformations which are mappings between functors.

Action on objects

Our fixed object $a \in C$ is mapped to $F(a) \in D$ and $G(a) \in D$ by our two functors.

For $a$, our natural transformation $\alpha$ is a map $\alpha_a := F(a) \to G(a)$, a morphism in $D$ taking an object in $D$ to another object in $D$.

So for any object $a \in C$, a natural transformation $\alpha$ picks a morphism $\alpha_a := F(a) \to G(a)$ from $D$.

Action on morphisms

Consider a morphisms $f := a \to b \in C$. Our functors will map it the following way: $F(f) := F(a) \to F(b)$ and $G(f) := G(a) \to G(b)$.

Knowing that under our natural transformation $a$ goes to $\alpha_a := F(a) \to G(a)$ and $b$ goes to $\alpha_b := F(b) \to G(b)$, we impose a commuting square where:

$$G(f) \circ \alpha_a = \alpha_b \circ F(f)$$

So a morphism in $C$ will be mapped to a commuting square in $D$.

(I promise I’ll also upload a picture… #todo)

Naturality condition

Let’s recap the action of a natural transformation:

• objects in $C$ $\mapsto$ morphisms in $D$
• morphisms in $C$ $\mapsto$ commuting square in $D$.

This commutativity of squares is called the naturality condition and without it we can’t have natural transformations!

In simple terms, the naturality condition states that changing the container and then the elements inside — $G(f) \circ \alpha_a$ — is the same as changing the elements first and then the container — $\alpha_b \circ F(f)$.

Natural transformations in programming

Let’s come back to our previous model of natural transformations as mapping containers.

alpha :: forall a. F a -> G a

Notice how for a fixed object in $C$, we get a morphism, so the entire natural transformation over all objects in $C$ is a family of morphisms. alpha is just a polymorphc function.

Some examples:

-- Mapping from the List functor to the Maybe functor
safeHead :: [a] -> Maybe a

-- Mapping from the List functor to the Const functor
length :: [a] -> Const Int a

References

• Milewski, Bartosz. “Category Theory for Programmers,” 2014.