A personal blog about computer science topics.

Natural Transformation
A Morphism of Functors
Posted on Sep 12 2023 ~ 5 min read
#category theory  #haskell 

Let C \mathcal{C} and D \mathcal{D} be categories and F F and G G be functors C D \mathcal{C} \rightarrow \mathcal{D} . Then a natural transformation α \alpha from F F to G G is a family of morphism that satisfies the following requirements:

  • For every object A A in C \mathcal{C} , a natural transformation α \alpha from the functor F F to the functor G G assigns a morphism α A : F ( A ) G ( A ) \alpha_{A} : F(A) \rightarrow G(A) between objects of D \mathcal{D} . The morphism α A \alpha_{A} is called the component of α \alpha at A A .

  • Components must be such that for every morphism f : A B f : A \rightarrow B in C \mathcal{C} we have: α B F ( f ) = G ( f ) α A \alpha_{B} \circ F(f) = G(f) \circ \alpha_{A} (naturality condition)

These requirements can be expressed by the following commutative diagram:

\begin{xy} \xymatrix{ A \ar[r]_{F\ \ \ } \ar[d]_{f} \ar@/^1.5pc/[rr]^{\alpha_{A}\ \circ\ F} & F(A) \ar[r]_{\alpha_{A}} \ar[d]_{F(f)} & G(A) \ar[d]_{G(f)} \\ B \ar[r]^{F\ \ \ } \ar@/_1.5pc/[rr]_{\alpha_{B}\ \circ\ F} & F(B) \ar[r]^{\alpha_{B}} & G(B) } \end{xy}

Natural transformations are often denoted as double arrows, α : F G \alpha : F \Rightarrow G , to distinguish them in diagrams from usual morphisms:

\begin{xy} \xymatrix @=5pc { \mathcal{C} \rtwocell<5>^{F}_{G}{\alpha} & \mathcal{D} } \end{xy}

In other words, a natural transformation is a way of transforming one functor into another while respecting the internal structure of the categories involved. Natural transformations are one of the most important aspects of category theory. Saunders Mac Lane, one of the founders of category theory, once said:

I didn’t invent categories to study functors; I invented them to study natural transformations.


In Haskell, we can define a natural transformation like so:

class (Functor f, Functor g) => Transformation f g where
    alpha :: f a -> g a

Or we could also define it the following way, as an infix operator (~>):

{-# LANGUAGE TypeOperators #-}
{-# LANGUAGE RankNTypes    #-}

type ~> g = forall a . f a -> g a

Again, the requirement of compatibility with the actions of the functors is not expressible as a type signature, but we can write it down as law in pseudocode:

alpha (fmap f a) = fmap f (alpha a) -- (naturality condition)

Now Haskell supports parametric polymorphism, that means that a function will act on all types uniformly and thus automatically satisfies the naturality condition for any polymorphic function of the type:

alpha :: F a -> G a

where F and G are functors. The naturality condition in terms of Haskell means that it doesn’t matter whether we first apply a function, through the application of fmap, and then change the structure via a structure preserving mapping; or first change the structure, and then apply the function to the new structure, with its own implementation of fmap. [2]

Lets have a look at the following example:

safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:xs) = Just x

This function returns Nothing in case of an empty list and the first element of the list in case of an non-empty List. This function is called safeHead, because there is also a “unsafeHead” in the Haskell standard library, simply called head. The unsafe variant throws an Exception in case the List is empty. We can prove by equational reasoning (or Coq if you like) that the naturality condition holds in case of safeHead:

-- Proposition.
fmap f . safeHead = safeHead . fmap f

-- Case Nothing.
fmap f (safeHead []) = fmap f Nothing = Nothing
safeHead (fmap f []) = safeHead [] = Nothing

-- Case non-empty List.
fmap f (safeHead (x:xs)) = fmap f (Just x) = Just (f x)
safeHead (fmap f (x:xs)) = safeHead (f x : fmap f xs) = Just (f x)

-- Qed.

Here are some more natural transformations:

eitherToMaybe :: Either a b -> Maybe b
eitherToMaybe (Left _)  = Nothing
eitherToMaybe (Right x) = Just x

identityToMaybe :: Identity a -> Maybe a
identityToMaybe (Identity x) = Just x

maybeToList  :: Maybe a -> [a]
maybeToList  Nothing   = []
maybeToList  (Just x)  = [x]

maybeToList2 :: Maybe a -> [a]
maybeToList2 Nothing = []
maybeToList2 (Just x) = [x,x]

maybeToList3 :: Maybe a -> [a]
maybeToList3 Nothing = []
maybeToList3 (Just x) = [x,x,x]

-- ...

As we can see there is an infinite number of natural transformations.

You can open an interactive Haskell interpreter (ghci), load the functions and test the following examples.

ghci> safeHead [1,2,3]
Just 1

ghci> safeHead []

ghci> maybeToList2 Nothing

ghci> maybeToList3 (Just "Hi")


  1. 1.Mac Lane, Saunders (1998), Categories for the Working Mathematician, Graduate Texts in Mathematics 5 (2nd ed.), Springer-Verlag, p. 16, ISBN 0-387-98403-8
  2. 2.Natural Transformations by Bartosz Milewski (2015)