Natural transformations

In category theory:

  • Morphisms compare objects.
  • Functors compare categories.
  • Natural transformations compare functors.

Given two functors FF and GG that each map from a source category SrcSrc to a target category TgtTgt we want to find a way to compare the two functors. We can do this if they have the same variance and they map in the same direction.

Given an object ASrcA \in Src, the two functors map that AA to FATgtF A \in Tgt and GATgtG A \in Tgt. We compare these two objects in the target category which means there is a morphism that we define as a natural transformation τ\tau which is a family of morphisms of the target category that are indexed by the objects of the source category.

FAτAGAF A \xrightarrow {\tau A} G A

In addition, for each morphism AfBA \xrightarrow {f} B, we have the following commuting squares:

By composing the sides of the diagram we can get from FAFA to GAGA in two ways (here we look at the covariant side of the diagram above):

GfτA=τBFfGf \circ \tau_A = \tau_B \circ Ff

This is called the naturality condition which holds for any morphism ff. If FfFf is invertible this means that τB\tau_B can be defined in terms of τA\tau_A (and vice-versa):

τB=GfτA(Ff)1\tau_B = Gf \circ \tau_A \circ (Ff)^{-1}

Given a natural transformation in which all the components are isomorphisms (invertible morphisms) we say this is a natural isomorphism. This means isomorphic functors - they are similar.

Natural transformations in Haskell

Endofunctors in Haskell are type constructors that map types to types and functions to functions (by fmapfmap). Given two functors FF and GG we define a natural transformation in Haskell as a polymorphic function for all types aa:

This is really a family of functions parameterized by type aa.

The naturality condition is automatically satisfied in Haskell by virtue of the nature of polymorphic functions being defined for all types (parametric polymorphism). Therefore:

We went over the idea of functors being contexts or containers and the action of some function on a container changes the contents but not the structure. Natural transformations change the structure of the containers while leaving the contents untouched.

The naturality condition says that it doesn't matter in which order we perform this composition, we can apply the function to the contents first, then modify the structure which is equivalent to first modifying the structure and then applying the function to this modified structure.

An example of a natural transformation is safeHeadsafeHead:

This is because it is parametrically polymorphic and so is a natural transformation. We can verify the naturality condition:

Even some functions that don't look like natural transformations can actually be expressed so. For example:

from the Prelude library can be expressed as:

which is a natural transformation!