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

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

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

These requirements can be expressed by the following commutative diagram:

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

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.

Example

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 f ~> 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 []
Nothing

ghci> maybeToList2 Nothing
[]

ghci> maybeToList3 (Just "Hi")
["Hi","Hi","Hi"]

References