Functors and natural transformations

Functors

A functor is a structure-preserving map between categories. Given categories $\mathcal{C}$ and $\mathcal{D}$, a functor $F : \mathcal{C} \to \mathcal{D}$ consists of:

An object mapping: For each object $A$ in $\mathcal{C}$, an object $F(A)$ in $\mathcal{D}$
A morphism mapping: For each morphism $f : A \to B$ in $\mathcal{C}$, a morphism $F(f) : F(A) \to F(B)$ in $\mathcal{D}$

Functor Laws

Functors must preserve categorical structure:

Preservation of Identity: $F(\text{id}_A) = \text{id}_{F(A)}$
Preservation of Composition: $F(g \circ f) = F(g) \circ F(f)$

Examples of Functors

1. The List Functor

In programming, the list type constructor is a functor:

Verification of Functor Laws:

Identity: fmap id == id
Composition: fmap (g . f) == fmap g . fmap f

2. The Maybe Functor

Represents computations that might fail:

3. The Function Functor

Functions from a fixed type form a functor:

This is function composition as a functor.

4. Contravariant Functors

A contravariant functor reverses the direction of morphisms:

\[F(f : A \to B) : F(B) \to F(A)\]

Example: The Predicate functor:

Natural Transformations

A natural transformation is a structure-preserving map between functors. Given functors $F, G : \mathcal{C} \to \mathcal{D}$, a natural transformation $\eta : F \Rightarrow G$ is a family of morphisms:

\[\eta_A : F(A) \to G(A)\]

for each object $A$ in $\mathcal{C}$, such that for any morphism $f : A \to B$ in $\mathcal{C}$:

\[G(f) \circ \eta_A = \eta_B \circ F(f)\]

This commutative diagram is called the naturality condition:

\[\begin{CD} F(A) @>F(f)>> F(B)\\ @V\eta_AVV @VV\eta_BV\\ G(A) @>>G(f)> G(B) \end{CD}\]

Examples of Natural Transformations

1. List to Maybe

Converting a list to its first element:

Naturality: For any function f :: a -> b:

2. Reverse

The list reverse function is a natural transformation from the list functor to itself:

Naturality: For any function f :: a -> b:

Proof:

3. Flatten/Join

For nested structures:

Non-Example: Length

The length function is not a natural transformation because it doesn’t preserve the type:

While polymorphic, it violates naturality:

Functor Composition

Functors compose: if $F : \mathcal{C} \to \mathcal{D}$ and $G : \mathcal{D} \to \mathcal{E}$, then $G \circ F : \mathcal{C} \to \mathcal{E}$ is a functor.

Bifunctors

A bifunctor is a functor of two arguments:

Examples:

Pairs: (,)
Either: Either
Functions: (->) (contravariant in first argument, covariant in second)

Applicative Functors

An applicative functor is a functor with additional structure for applying functions wrapped in the functor:

Applicative Laws

Identity: pure id <*> v = v
Composition: pure (.) <*> u <*> v <*> w = u <*> (v <*> w)
Homomorphism: pure f <*> pure x = pure (f x)
Interchange: u <*> pure y = pure ($ y) <*> u

Examples

Maybe Applicative

Usage:

List Applicative

Usage:

Applicative vs Functor

Functor: Apply a pure function to a wrapped value
Applicative: Apply a wrapped function to a wrapped value

Applicatives allow combining multiple independent effectful computations:

The Yoneda Lemma

One of the most important results in category theory states that natural transformations from $\text{Hom}(A, -)$ to a functor $F$ are in one-to-one correspondence with elements of $F(A)$.

In programming terms:

This has practical implications for optimization and generic programming.

Exercises

Verify that the Maybe functor satisfies both functor laws:
- Identity: fmap id = id
- Composition: fmap (g . f) = fmap g . fmap f
Implement a Tree data type and its Functor instance:
Prove that the function reverse :: [a] -> [a] is a natural transformation.
Implement Functor instance for:
Show that the composition of two functors is also a functor.
Prove or disprove: The function null :: [a] -> Bool is a natural transformation from the list functor to the constant functor.
Implement the Applicative instance for: where (<*>) zips lists together rather than taking the Cartesian product.
Show that every monad gives rise to an applicative functor.
Define a bifunctor instance for a custom data type of your choice.
Using the Applicative interface, write a function that validates three fields of a form and combines the results:

See: