Natural transformation
Functor morphisms. polymorphism
_ _ _ _____ _ _ ____ _ _
| \ | | / \|_ _| | | | _ \ / \ | |
| \| | / _ \ | | | | | | |_) | / _ \ | |
| |\ |/ ___ \| | | |_| | _ < / ___ \| |___
|_|_\_/_/__ \_\_|_ \___/|_| \_\/_/___\_\_____|___ __ __ _ _____ ___ ___ _ _ ____
|_ _| _ \ / \ | \ | / ___|| ___/ _ \| _ \| \/ | / \|_ _|_ _/ _ \| \ | / ___|
| | | |_) | / _ \ | \| \___ \| |_ | | | | |_) | |\/| | / _ \ | | | | | | | \| \___ \
| | | _ < / ___ \| |\ |___) | _|| |_| | _ <| | | |/ ___ \| | | | |_| | |\ |___) |
|_| |_| \_\/_/ \_\_| \_|____/|_| \___/|_| \_\_| |_/_/ \_\_| |___\___/|_| \_|____/
Introduction #
You might have guessed this one already. As soon as we have some sort of concept, we tend to generalize it by understanding its relation to itself and other objects of the same nature. We categorized morphisms and objects. There is no reason to leave functors behind. Once we have functors mapping between categories, a natural question arises: How do functors relate to each other? If we have two functors F and G both going from category C to category D, what does it mean for them to be "connected" in a meaningful way?
This is where natural transformations come in. They are morphisms between functors—systematic ways to transform one functor into another while respecting the categorical structure. The word "natural" captures something profound about transformations that work "the same way" regardless of the specific objects involved.
Consider a simple programming example: converting a list to its length. This operation works for lists of any type—List<Int>, List<String>, List<Bool>—and the transformation behaves consistently across all types. This consistency is what makes it "natural." In contrast, an operation that behaves differently for different types (like choosing the "first" element based on some arbitrary ordering) would not be natural.
Natural transformations formalize this intuitive notion of "canonical" or "systematic" transformations:
- Converting between different data representations
- Extracting information from data structures
- Composing operations that work across multiple contexts
- Defining interfaces that work generically across types
Formal definition #
A natural transformation is a way of transforming one functor into another while preserving the structure of the categories involved.
Definition #
Given two functors F and G both mapping from category C to category D:
F: C -> DG: C -> D
A natural transformation η: F ⟹ G (read as "eta from F to G") consists of:
-
Component morphisms: For each object
Ain categoryC, there is a morphismη_A: F(A) -> G(A)in categoryD. -
Naturality condition: For every morphism
f: A -> Bin categoryC, the following diagram commutes:
F(A) ---F(f)---> F(B)
| |
|η_A |η_B
| |
▼ ▼
G(A) ---G(f)---> G(B)
This means: η_B ∘ F(f) = G(f) ∘ η_A
-
Component morphisms (
η_A): Think of these as a "recipe" that works for every object. For each objectAin the source category, we have a specific morphismη_Athat transformsF(A)intoG(A). -
Naturality condition: This is the crucial constraint that makes the transformation "natural." It says that no matter which path you take through the diagram—whether you:
- Apply
F(f)first, thenη_B, OR - Apply
η_Afirst, thenG(f)
- Apply
...you get the same result.
This consistency across all morphisms is what distinguishes natural transformations from arbitrary collections of morphisms.
Properties #
-
Identity Natural Transformation: For any functor
F: C → D, there exists an identity natural transformationid_F: F ⟹ Fwhere each component is(id_F)_A = id_{F(A)}.Just like every object has an identity morphism, every functor has an identity natural transformation that "does nothing" to the functor. Each component simply maps
F(A)to itself using the identity morphism. This is like having a function that returns its input unchanged—it satisfies all the requirements of a natural transformation trivially because identity morphisms preserve all structure. -
Vertical composition: Given natural transformations
η: F ⟹ Gandμ: G ⟹ H, their (vertical) compositionμ ∘ η: F ⟹ His defined component-wise:(μ ∘ η)_A = μ_A ∘ η_A.You can chain natural transformations together, just like composing functions. If you have a way to transform functor
FintoG, and another way to transformGintoH, you can combine them to get a direct transformation fromFtoH. At each objectA, you simply compose the component morphisms in sequence. The naturality condition ensures this composition remains natural. -
Horizontal composition (whiskering): Natural transformations can be composed "horizontally" with functors.
If you have a natural transformation
η: F ⟹ Gbetween functors fromCtoD, and another functorH: D → E, you can "extend" the natural transformation by applyingHto getH ∘ η: H ∘ F ⟹ H ∘ G. Similarly, you can compose with functors on the left. This is called "horizontal" composition because you're composing along the direction of functor composition, allowing natural transformations to interact with the categorical structure in a systematic way.
The naturality condition captures what programmers intuitively mean when they say an operation works "generically" or "polymorphically." It formalizes the idea that the transformation doesn't depend on the specific structure of individual objects, but works uniformly across the entire category.
Examples #
Let's explore natural transformations through concrete examples that demonstrate how they work in practice across different programming languages.
List Length - A Simple Natural Transformation #
One of the most intuitive natural transformations is converting any list to its length. This transformation works uniformly across all list types.
-- The List functor
-- fmap :: (a -> b) -> [a] -> [b]
-- Natural transformation from List to Const Int
listLength :: [a] -> Int
listLength = length
-- Verification of naturality:
-- For any function f :: a -> b and list xs :: [a]:
-- listLength (fmap f xs) == listLength xs
-- This holds because length doesn't depend on the elements
-- Example usage:
example1 :: Bool
example1 = let f = (*2) :: Int -> Int
xs = [1, 2, 3] :: [Int]
in listLength (map f xs) == listLength xs -- True
main :: IO ()
main = print example1
// The Array functor (built into JavaScript/TypeScript)
// Array.map :: (a -> b) -> Array<a> -> Array<b>
// Natural transformation from Array to number
const arrayLength = <A>(arr: Array<A>): number => arr.length;
// Verification of naturality:
// For any function f: A -> B and array arr: Array<A>:
// arrayLength(arr.map(f)) === arrayLength(arr)
// Example usage:
const f = (x: number) => x * 2;
const arr = [1, 2, 3];
const natural = arrayLength(arr.map(f)) === arrayLength(arr); // true
console.log(`Naturality check: ${natural}`);
using System;
using System.Collections.Generic;
using System.Linq;
// The List/IEnumerable functor (Select method provides fmap)
// Select :: (A -> B) -> IEnumerable<A> -> IEnumerable<B>
public static class Program
{
// Natural transformation from IEnumerable to int
public static int EnumerableCount<T>(IEnumerable<T> source) => source.Count();
// Verification of naturality:
// For any function f: A -> B and enumerable source: IEnumerable<A>:
// EnumerableCount(source.Select(f)) == EnumerableCount(source)
public static void Main()
{
Func<int, string> f = x => (x * 2).ToString();
var list = new[] { 1, 2, 3 };
var natural = EnumerableCount(list.Select(f)) == EnumerableCount(list);
Console.WriteLine($"Naturality check: {natural}"); // True
}
}
Maybe/Option Head #
(Extracting First Element)
This natural transformation converts any non-empty list to its first element wrapped in a Maybe/Option type.
-- Natural transformation from List to Maybe
safeHead :: [a] -> Maybe a
safeHead [] = Nothing
safeHead (x:_) = Just x
-- Verification of naturality:
-- For any function f :: a -> b and list xs :: [a]:
-- fmap f (safeHead xs) == safeHead (fmap f xs)
-- Example:
example2 :: Bool
example2 = let f = show -- Int -> String
xs = [1, 2, 3] :: [Int]
in fmap f (safeHead xs) == safeHead (map f xs) -- True
main :: IO ()
main = print example2
// Option/Maybe type
type Option<A> = { tag: 'some'; value: A } | { tag: 'none' };
const some = <A>(value: A): Option<A> => ({ tag: 'some', value });
const none: Option<never> = { tag: 'none' };
// Natural transformation from Array to Option
const safeHead = <A>(arr: Array<A>): Option<A> =>
arr.length > 0 ? some(arr[0]!) : none;
// Option functor map
const mapOption = <A, B>(f: (a: A) => B, opt: Option<A>): Option<B> =>
opt.tag === 'some' ? some(f(opt.value)) : none;
// Verification of naturality:
// For any function f: A -> B and array arr: Array<A>:
// mapOption(f, safeHead(arr)) should equal safeHead(arr.map(f))
const f2 = (x: number) => x.toString();
const arr2 = [1, 2, 3];
const left = mapOption(f2, safeHead(arr2));
const right = safeHead(arr2.map(f2));
console.log(`Left: ${JSON.stringify(left)}`); // {"tag":"some","value":"1"}
console.log(`Right: ${JSON.stringify(right)}`); // {"tag":"some","value":"1"}
using System;
using System.Collections.Generic;
using System.Linq;
// Option/Maybe type
public abstract class Option<T>
{
public abstract Option<U> Map<U>(Func<T, U> f);
}
public class Some<T> : Option<T>
{
public T Value { get; }
public Some(T value) => Value = value;
public override Option<U> Map<U>(Func<T, U> f) => new Some<U>(f(Value));
}
public class None<T> : Option<T>
{
public override Option<U> Map<U>(Func<T, U> f) => new None<U>();
}
public static class Program
{
// Natural transformation from IEnumerable to Option
public static Option<T> SafeHead<T>(this IEnumerable<T> source)
{
using var enumerator = source.GetEnumerator();
return enumerator.MoveNext() ? new Some<T>(enumerator.Current) : new None<T>();
}
public static void Main()
{
Func<int, string> f = x => x.ToString();
var list = new[] { 1, 2, 3 };
// Verify naturality: fmap f (safeHead xs) == safeHead (fmap f xs)
var left = list.SafeHead().Map(f);
var right = list.Select(f).SafeHead();
Console.WriteLine($"Left: {(left is Some<string> s1 ? s1.Value : "None")}"); // "1"
Console.WriteLine($"Right: {(right is Some<string> s2 ? s2.Value : "None")}"); // "1"
}
}
Flatten #
(From Nested Structure to Flat Structure)
This natural transformation flattens nested structures, demonstrating how natural transformations can work with more complex functors.
-- Natural transformation from [[a]] to [a]
flatten :: [[a]] -> [a]
flatten = concat
-- Verification of naturality:
-- For any function f :: a -> b and nested list xss :: [[a]]:
-- map f (flatten xss) == flatten (map (map f) xss)
example3 :: Bool
example3 = let f = (*2) :: Int -> Int
xss = [[1, 2], [3, 4]] :: [[Int]]
in map f (flatten xss) == flatten (map (map f) xss) -- True
main :: IO ()
main = print example3
// Natural transformation from Array<Array<A>> to Array<A>
const flatten = <A>(nested: Array<Array<A>>): Array<A> =>
nested.reduce((acc, arr) => acc.concat(arr), [] as Array<A>);
// Verification of naturality:
const f3 = (x: number) => x * 2;
const nested = [[1, 2], [3, 4]];
const left3 = flatten(nested).map(f3);
const right3 = flatten(nested.map(arr => arr.map(f3)));
console.log(`Flatten naturality: ${JSON.stringify(left3) === JSON.stringify(right3)}`);
console.log(`Left: [${left3.join(', ')}]`); // [2, 4, 6, 8]
console.log(`Right: [${right3.join(', ')}]`); // [2, 4, 6, 8]
using System;
using System.Collections.Generic;
using System.Linq;
public static class Program
{
// Natural transformation from IEnumerable<IEnumerable<T>> to IEnumerable<T>
public static IEnumerable<T> Flatten<T>(IEnumerable<IEnumerable<T>> nested) =>
nested.SelectMany(x => x);
public static void Main()
{
Func<int, int> f = x => x * 2;
var nested = new[] { new[] { 1, 2 }, new[] { 3, 4 } };
// Verify naturality: fmap f (flatten xss) == flatten (fmap (fmap f) xss)
var left = Flatten(nested).Select(f);
var right = Flatten(nested.Select(inner => inner.Select(f)));
Console.WriteLine($"Flatten naturality: {left.SequenceEqual(right)}");
Console.WriteLine($"Left: [{string.Join(", ", left)}]"); // [2, 4, 6, 8]
Console.WriteLine($"Right: [{string.Join(", ", right)}]"); // [2, 4, 6, 8]
}
}
Triangle Example #
(Perimeter to √Area Natural Transformation)
Let's illustrate natural transformations with a geometric example involving triangles, similar to how we explored functors.
Consider two functors that both map from the category of Triangles (with geometric transformations as morphisms) to the category of Real Numbers (with multiplication as morphisms):
- Perimeter Functor (
Perim): Maps each triangle to its perimeter, and each scaling transformation by factorkto multiplication byk. - Root-Area Functor (
RootArea): Maps each triangle to√(Area(T)). Under scaling byk, area scales byk², so√(Area)scales byk(again: multiplication byk).
Now, there's a natural transformation η: Perim ⟹ RootArea that relates perimeter to √(area) systematically across all triangles.
For any triangle T, define the component η_T to be "multiply by the constant" √(Area(T)) / Perimeter(T).
where √ is a square root.
This transformation has the naturality property: when you scale a triangle by factor k, it doesn't matter whether you:
- Apply the perimeter-to-
√(area)conversion first, then scale, OR - Scale first, then apply the conversion
Let's verify this with a concrete example:
Original triangle: Vertices at (0,0), (3,0), (0,4) - a right triangle
- Area: 6 square units
- Perimeter: 12 units
η_T = √6 / 12 ≈ 0.204
After scaling by factor 2: Vertices at (0,0), (6,0), (0,8)
- Area: 24 square units (scaled by
2² = 4) - Perimeter: 24 units (scaled by 2)
η_T' = √24 / 24 ≈ 0.204
The ratio remains constant! This demonstrates naturality: the transformation works consistently regardless of which geometric transformations we apply.
Category of Triangles → Category of Real Numbers
Triangle T ----scale k----> T' Perim(T) ----×k----> Perim(T')
| | | |
|η_T |η_T' |η |η
| | | |
▼ ▼ ▼ ▼
Triangle T ----scale k----> T' √Area(T) ----×k----> √Area(T')
The commutative diagram shows: η_T' ∘ (×k) = (×k) ∘ η_T
This naturality condition captures what we intuitively expect: the relationship between perimeter and √(area) should be "geometric" - it shouldn't depend on arbitrary choices about coordinate systems or scale, but should work uniformly across all triangles and all geometric transformations.
Visualizing natural transformations #
1. Systematic "bridge" between two functors
Category C Category D
A ----f---> B F(A) ---F(f)---> F(B)
│ │ │ │
│ η │ │ η_A │ η_B
│ bridge │ │ │
▼ ▼ ▼ ▼
A ----f---> B G(A) ---G(f)---> G(B)
The η bridge connects every F(A) to G(A) in a way that
"commutes" with all the traffic patterns f in category C.
It's a bridge that respects the traffic patterns (morphisms) of the underlying categories.
2. The Recipe
Raw Ingredients (F) Prepared Dishes (G)
↓ η recipe ↓
Tomatoes ---------------> Tomato Sauce
│ │
│ "dice & simmer" │ same process
│ │
Onions ---------------> Onion Sauce
The η recipe (dice & simmer) works for any ingredient,
and combining ingredients works the same way before or
after applying the recipe (naturality condition)
3. The Commutative Square
F(A) ----F(f)----> F(B)
│ │
η_A│ η_B│
│ │
▼ ▼
G(A) ----G(f)----> G(B)
This means: G(f) ∘ η_A = η_B ∘ F(f)
"map then transform" equals "transform then map"
Conclusion #
naturality = systematic consistency
A natural transformation works the same way everywhere, respecting the categorical structure without making arbitrary choices that depend on specific objects or morphisms.
Think of it as the difference between:
- Natural: "Take the length of any list" (works uniformly)
- Unnatural: "Take the 'best' element from any list" (requires arbitrary choices)
Natural transformations formalize what programmers mean when they say an operation works "generically" or "polymorphically."
Source code #
Reference implementation (opens in a new tab)