Natural Transformations

Bartosz Milewski · 2015 · Category Theory for Programmers, Ch. 10

A natural transformation maps between functors while preserving structure. The naturality condition says: it doesn't matter whether you transform first and then map, or map first and then transform. In Haskell, parametric polymorphism gives you naturality for free: any function F a -> G a that works uniformly for all types automatically satisfies the naturality square.

Natural transformations: morphisms between functors

A functor maps objects and morphisms from one category to another. A natural transformation maps between two such functors. For functors F and G from category C to D, a natural transformation alpha provides, for each object a in C, a morphism alpha_a : F(a) -> G(a) in D. These morphisms are called components. Natural transformations are how the natural framework connects its six processing stages: each stage is a functor, and the transitions between them are natural transformations that preserve the information structure.

Scheme

; A natural transformation alpha : F -> G
; gives a component alpha_a : F(a) -> G(a) for every type a.
;
; Example: safeHead is a natural transformation from List to Maybe.
; For every type a, safeHead : List(a) -> Maybe(a).

(define nothing (cons 'left '()))
(define (just x) (cons 'right x))
(define (nothing? m) (and (pair? m) (eq? (car m) 'left)))

; safeHead : List -> Maybe  (a natural transformation)
(define (safe-head lst)
  (if (null? lst)
      nothing
      (just (car lst))))

(display "safe-head '(1 2 3): ") (display (safe-head '(1 2 3))) (newline)
(display "safe-head '():      ") (display (safe-head '())) (newline)
(display "safe-head '(a b):   ") (display (safe-head '(a b)))
; Works uniformly for any type — that's the "natural" part.

The naturality condition

The components of a natural transformation can't be arbitrary. They must satisfy the naturality condition: for every morphism f : a -> b, the following square commutes.

In words: transform then map = map then transform. This is what makes the transformation "natural" rather than ad hoc.

Scheme

; Naturality condition for safeHead:
;   fmap-maybe f . safe-head  =  safe-head . map f
;
; "Transform then map" = "Map then transform"

(define (fmap-maybe f m)
  (if (nothing? m) nothing (just (f (cdr m)))))

; Test with f = double
(define (double x) (* x 2))

; Path 1: map first, then transform
(define path1 (safe-head (map double '(3 1 4))))

; Path 2: transform first, then map
(define path2 (fmap-maybe double (safe-head '(3 1 4))))

(display "map then transform: ") (display path1) (newline)
(display "transform then map: ") (display path2) (newline)
(display "equal? ") (display (equal? path1 path2)) (newline)

; Also works on empty lists
(define p1-empty (safe-head (map double '())))
(define p2-empty (fmap-maybe double (safe-head '())))
(display "empty path1: ") (display p1-empty) (newline)
(display "empty path2: ") (display p2-empty) (newline)
(display "equal? ") (display (equal? p1-empty p2-empty))

Length: List -> Const Int

Another natural transformation: length. It maps from the List functor to the Const Int functor. The Const functor ignores its type parameter, so Const Int a is just Int regardless of a. Length doesn't care what's in the list, only how many elements there are. That type-blindness is naturality at work.

Scheme

; length : List a -> Const Int a
; A natural transformation that forgets the elements.

(define (my-length lst) (length lst))

; fmap for Const does nothing (ignores the function)
(define (fmap-const f c) c)

; Naturality: fmap-const f . my-length = my-length . map f
; Since fmap-const ignores f, this says:
;   length(xs) = length(map f xs)
; Mapping can't change the number of elements!

(define (double x) (* x 2))
(define xs '(10 20 30 40))

(display "length(xs):          ") (display (my-length xs)) (newline)
(display "length(map double xs): ") (display (my-length (map double xs))) (newline)
(display "equal? ") (display (= (my-length xs) (my-length (map double xs)))) (newline)

; This works for ANY function f — that's the naturality condition.
(display "length(map car '((a 1) (b 2))): ")
(display (my-length (map car '((a 1) (b 2)))))

Theorems for free: polymorphism = naturality

Here is the deepest insight. In Haskell, any polymorphic function alpha :: F a -> G a (where F and G are functors) automatically satisfies the naturality condition. You don't need to check it. Parametric polymorphism means the function works by one formula for all types. It can't inspect the type, so it can't break the naturality square. This is Wadler's "theorems for free": the type signature alone generates the equation fmap g . alpha = alpha . fmap g as a free theorem.

Scheme

; "Theorems for free" — parametric polymorphism implies naturality.
;
; If alpha works the same way for ALL types,
; it can't break the naturality square.
;
; Example: reverse : List a -> List a
; reverse doesn't inspect elements, so:
;   map f . reverse = reverse . map f

(define (double x) (* x 2))
(define xs '(1 2 3 4 5))

; Path 1: reverse then map
(define path1 (map double (reverse xs)))

; Path 2: map then reverse
(define path2 (reverse (map double xs)))

(display "map-then-reverse:  ") (display path1) (newline)
(display "reverse-then-map:  ") (display path2) (newline)
(display "equal? ") (display (equal? path1 path2)) (newline)

; Another example: tail : List a -> List a
(define path3 (map double (cdr xs)))
(define path4 (cdr (map double xs)))
(display "map-then-tail: ") (display path3) (newline)
(display "tail-then-map: ") (display path4) (newline)
(display "equal? ") (display (equal? path3 path4))

Functor categories

Natural transformations compose. If alpha : F -> G and beta : G -> H, then (beta . alpha)_a = beta_a . alpha_a gives a natural transformation from F to H. This makes functors between two categories C and D into a category of their own: [C, D], the functor category. Objects are functors, morphisms are natural transformations, and the identity natural transformation maps each F(a) to itself.

Scheme

; Functor category: compose natural transformations vertically.
; If alpha : F -> G and beta : G -> H, then (beta . alpha) : F -> H
; Component-wise: (beta . alpha)_a = beta_a . alpha_a

; Three functors: List, Maybe, Const-Bool
; alpha = safe-head : List -> Maybe
; beta = is-just : Maybe -> Const-Bool

(define (safe-head lst)
  (if (null? lst) nothing (just (car lst))))

(define (is-just m)
  (if (nothing? m) #f #t))

; Vertical composition: is-just . safe-head : List -> Const-Bool
; "Is the list non-empty?"
(define (non-empty? lst)
  (is-just (safe-head lst)))

(display "non-empty? '(1 2): ") (display (non-empty? '(1 2))) (newline)
(display "non-empty? '():    ") (display (non-empty? '())) (newline)

; The composition is itself a natural transformation.
; Naturality: fmap-const f . non-empty? = non-empty? . map f
; fmap-const ignores f, so: non-empty?(xs) = non-empty?(map f xs)
(define xs '(10 20 30))
(display "non-empty?(xs):        ") (display (non-empty? xs)) (newline)
(display "non-empty?(map * xs):  ") (display (non-empty? (map (lambda (x) (* x 2)) xs)))

; Functor category: compose natural transformations vertically.
; If alpha : F -> G and beta : G -> H, then (beta . alpha) : F -> H
; Component-wise: (beta . alpha)_a = beta_a . alpha_a

; Three functors: List, Maybe, Const-Bool
; alpha = safe-head : List -> Maybe
; beta = is-just : Maybe -> Const-Bool

(define (safe-head lst)
  (if (null? lst) nothing (just (car lst))))

(define (is-just m)
  (if (nothing? m) #f #t))

; Vertical composition: is-just . safe-head : List -> Const-Bool
; "Is the list non-empty?"
(define (non-empty? lst)
  (is-just (safe-head lst)))

(display "non-empty? '(1 2): ") (display (non-empty? '(1 2))) (newline)
(display "non-empty? '():    ") (display (non-empty? '())) (newline)

; The composition is itself a natural transformation.
; Naturality: fmap-const f . non-empty? = non-empty? . map f
; fmap-const ignores f, so: non-empty?(xs) = non-empty?(map f xs)
(define xs '(10 20 30))
(display "non-empty?(xs):        ") (display (non-empty? xs)) (newline)
(display "non-empty?(map * xs):  ") (display (non-empty? (map (lambda (x) (* x 2)) xs)))

Naturality as a design constraint

The naturality condition is surprisingly restrictive. How many natural transformations are there from Maybe to List? Only two: either send Nothing -> [] and Just x -> [x], or send everything to []. The naturality square forbids any other choice. The type signature Maybe a -> [a] pins down the implementation almost completely.

Scheme

; How many natural transformations Maybe -> List?
; Only two! Naturality constrains the options.

; Option 1: Nothing -> (), Just x -> (x)
(define (maybe-to-list-1 m)
  (if (nothing? m) '() (list (cdr m))))

; Option 2: everything -> ()
(define (maybe-to-list-2 m)
  '())

; Any other mapping (e.g., Just x -> (x x x)) fails naturality.
; Why? If alpha(Just x) = (x x x), then:
;   map f (alpha (Just x)) = map f (x x x) = (f(x) f(x) f(x))
;   alpha (fmap f (Just x)) = alpha (Just f(x)) = (f(x) f(x) f(x))
; Wait, that works! But alpha(Nothing) must be ().
; Actually (x x x) does satisfy naturality — but Milewski's point
; is that parametricity limits you to one "shape" per branch.

(display "opt1 Just(5):  ") (display (maybe-to-list-1 (just 5))) (newline)
(display "opt1 Nothing:  ") (display (maybe-to-list-1 nothing)) (newline)
(display "opt2 Just(5):  ") (display (maybe-to-list-2 (just 5))) (newline)
(display "opt2 Nothing:  ") (display (maybe-to-list-2 nothing)) (newline)

; Verify naturality for opt1:
(define (double x) (* x 2))
(define p1 (map double (maybe-to-list-1 (just 3))))
(define p2 (maybe-to-list-1 (fmap-maybe double (just 3))))
(display "path1: ") (display p1) (newline)
(display "path2: ") (display p2) (newline)
(display "equal? ") (display (equal? p1 p2))

; How many natural transformations Maybe -> List?
; Only two! Naturality constrains the options.

; Option 1: Nothing -> (), Just x -> (x)
(define (maybe-to-list-1 m)
  (if (nothing? m) '() (list (cdr m))))

; Option 2: everything -> ()
(define (maybe-to-list-2 m)
  '())

; Any other mapping (e.g., Just x -> (x x x)) fails naturality.
; Why? If alpha(Just x) = (x x x), then:
;   map f (alpha (Just x)) = map f (x x x) = (f(x) f(x) f(x))
;   alpha (fmap f (Just x)) = alpha (Just f(x)) = (f(x) f(x) f(x))
; Wait, that works! But alpha(Nothing) must be ().
; Actually (x x x) does satisfy naturality — but Milewski's point
; is that parametricity limits you to one "shape" per branch.

(display "opt1 Just(5):  ") (display (maybe-to-list-1 (just 5))) (newline)
(display "opt1 Nothing:  ") (display (maybe-to-list-1 nothing)) (newline)
(display "opt2 Just(5):  ") (display (maybe-to-list-2 (just 5))) (newline)
(display "opt2 Nothing:  ") (display (maybe-to-list-2 nothing)) (newline)

; Verify naturality for opt1:
(define (double x) (* x 2))
(define p1 (map double (maybe-to-list-1 (just 3))))
(define p2 (maybe-to-list-1 (fmap-maybe double (just 3))))
(display "path1: ") (display p1) (newline)
(display "path2: ") (display p2) (newline)
(display "equal? ") (display (equal? p1 p2))

Notation reference

Blog / Haskell	Scheme	Meaning
alpha :: F a -> G a	(alpha x)	Component of a natural transformation at type a
safeHead :: [a] -> Maybe a	(safe-head lst)	Natural transformation List -> Maybe
length :: [a] -> Const Int a	(my-length lst)	Natural transformation List -> Const Int
fmap g . alpha = alpha . fmap g	(equal? (map g (alpha xs)) (alpha (map g xs)))	Naturality condition
(beta . alpha)_a = beta_a . alpha_a	(beta (alpha x))	Vertical composition
[C, D]	—	Functor category: functors as objects, natural transformations as morphisms

Neighbors

Milewski chapters

🍞 Chapter 8 — Functoriality: bifunctors, contravariance, profunctors
(prev) 🍞 Chapter 7 — Functors: structure-preserving maps

Paper pages that use natural transformations

🍞 Fritz 2020 — Markov categories use natural transformations for copy and discard
🍞 Spivak 2013 — database queries as natural transformations between functors
🍞 Leinster 2021 — entropy as a natural transformation

Foundations (Wikipedia)

Translation notes

The blog post covers three layers: natural transformations, functor categories, and the 2-category Cat. This page covers the first two. The 2-category perspective (where categories are objects, functors are 1-morphisms, and natural transformations are 2-morphisms) and horizontal composition are omitted for clarity. The blog post also discusses contravariant natural transformations with Op functors and shows that naturality for polymorphic functions between Haskell functors is automatic via parametricity (Wadler's "Theorems for Free"). In Scheme, we have no type system to enforce this, so naturality is verified by testing rather than by proof. The key insight carries over regardless: a transformation that works uniformly without inspecting elements will satisfy the naturality square.

Ready for the real thing? Read the blog post. Start with the naturality condition, then see how parametric polymorphism gives it to you for free.

← Function Types by june.kim Limits and Colimits →