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:

1. An object mapping: For each object $A$ in $\mathcal{C}$, an object $F(A)$ in $\mathcal{D}$
2. 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:

1. Preservation of Identity: \(F(\text{id}_A) = \text{id}_{F(A)}\)

2. 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:

-- Haskell
instance Functor [] where
  fmap :: (a -> b) -> [a] -> [b]
  fmap f []     = []
  fmap f (x:xs) = f x : fmap f xs

// JavaScript
Array.prototype.map = function(f) {
  return this.map(f);  // Built-in map is fmap
}

Verification of Functor Laws:

1. Identity: fmap id == id

   fmap id [1,2,3] = [id 1, id 2, id 3] = [1,2,3]
   

2. Composition: fmap (g . f) == fmap g . fmap f

   fmap (g . f) [x] = [(g . f) x] = [g (f x)]
   fmap g (fmap f [x]) = fmap g [f x] = [g (f x)]
   

2. The Maybe Functor

Represents computations that might fail:

data Maybe a = Nothing | Just a

instance Functor Maybe where
  fmap f Nothing  = Nothing
  fmap f (Just x) = Just (f x)

3. The Function Functor

Functions from a fixed type form a functor:

instance Functor ((->) r) where
  fmap f g = f . g  -- Function composition

This is function composition as a functor.

4. Contravariant Functors

A contravariant functor reverses the direction of morphisms:

Example: The Predicate functor:

newtype Predicate a = Predicate { runPredicate :: a -> Bool }

instance Contravariant Predicate where
  contramap :: (a -> b) -> Predicate b -> Predicate a
  contramap f (Predicate p) = Predicate (p . f)

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:

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

This commutative diagram is called the naturality condition:

Examples of Natural Transformations

1. List to Maybe

Converting a list to its first element:

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

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

fmap f (safeHead xs) = safeHead (fmap f xs)

2. Reverse

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

reverse :: [a] -> [a]

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

fmap f (reverse xs) = reverse (fmap f xs)

Proof:

-- Both sides apply f to each element, then reverse
fmap f (reverse [x,y,z]) = fmap f [z,y,x] = [f z, f y, f x]
reverse (fmap f [x,y,z]) = reverse [f x, f y, f z] = [f z, f y, f x]

3. Flatten/Join

For nested structures:

join :: Monad m => m (m a) -> m a

-- For lists
join [[1,2],[3],[4,5]] = [1,2,3,4,5]

-- For Maybe
join (Just (Just x)) = Just x
join (Just Nothing)  = Nothing
join Nothing         = Nothing

Non-Example: Length

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

length :: [a] -> Int

While polymorphic, it violates naturality:

length (fmap f xs) = length xs  -- Always true
fmap f (length xs) = f (length xs)  -- Type error!

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.

-- Composing Maybe and List
newtype Compose f g a = Compose { getCompose :: f (g a) }

instance (Functor f, Functor g) => Functor (Compose f g) where
  fmap f (Compose x) = Compose (fmap (fmap f) x)

-- Example: Compose Maybe []
type MaybeList a = Compose Maybe [] a

example :: MaybeList Int
example = Compose (Just [1,2,3])

Bifunctors

A bifunctor is a functor of two arguments:

class Bifunctor p where
  bimap :: (a -> b) -> (c -> d) -> p a c -> p b d
  first :: (a -> b) -> p a c -> p b c
  second :: (c -> d) -> p a c -> p a d

Examples:

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

instance Bifunctor (,) where
  bimap f g (x, y) = (f x, g y)

instance Bifunctor Either where
  bimap f g (Left x)  = Left (f x)
  bimap f g (Right y) = Right (g y)

Applicative Functors

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

class Functor f => Applicative f where
  pure  :: a -> f a
  (<*>) :: f (a -> b) -> f a -> f b

Applicative Laws

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

Examples

Maybe Applicative

instance Applicative Maybe where
  pure = Just
  Nothing <*> _ = Nothing
  (Just f) <*> something = fmap f something

Usage:

-- Applying a function in Maybe to a value in Maybe
Just (+3) <*> Just 2 = Just 5
Nothing <*> Just 2 = Nothing

List Applicative

instance Applicative [] where
  pure x = [x]
  fs <*> xs = [f x | f <- fs, x <- xs]

Usage:

[(+1), (*2)] <*> [1,2,3]
-- Result: [2,3,4,2,4,6]

Applicative vs Functor

• Functor: Apply a pure function to a wrapped value

  fmap :: (a -> b) -> f a -> f b
  

• Applicative: Apply a wrapped function to a wrapped value

  (<*>) :: f (a -> b) -> f a -> f b
  

Applicatives allow combining multiple independent effectful computations:

-- Without applicative
fmap f (Just 1)  -- Can only apply pure function

-- With applicative
pure (+) <*> Just 1 <*> Just 2  -- Result: Just 3

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:

-- These two types are isomorphic
forall b. (a -> b) -> f b  ≅  f a

This has practical implications for optimization and generic programming.

Exercises

1. Verify that the Maybe functor satisfies both functor laws:
   • Identity: fmap id = id
   • Composition: fmap (g . f) = fmap g . fmap f
2. Implement a Tree data type and its Functor instance:

   data Tree a = Leaf a | Node (Tree a) (Tree a)
   

3. Prove that the function reverse :: [a] -> [a] is a natural transformation.

4. Implement Functor instance for:

   data Pair a = Pair a a
   

5. Show that the composition of two functors is also a functor.

6. Prove or disprove: The function null :: [a] -> Bool is a natural transformation from the list functor to the constant functor.

7. Implement the Applicative instance for:

   data ZipList a = ZipList [a]
   

   where (<*>) zips lists together rather than taking the Cartesian product.

8. Show that every monad gives rise to an applicative functor.

9. Define a bifunctor instance for a custom data type of your choice.

10. Using the Applicative interface, write a function that validates three fields of a form and combines the results:

    validateForm :: String -> String -> String -> Maybe User
    

See:

• Introduction to Categories
• Monads and Applicatives
• Categories in Programming