Module 3: Functors and Natural Transformations
If categories are the objects of study, functors are the maps between them. This module develops the concept of structure-preserving maps between categories, then goes one level higher: natural transformations are maps between functors. You will see that graph homomorphisms, typed API mappings, and polymorphic functions in any language are all instances of the same abstract construction. The module closes by constructing the functor category, which is itself a category — establishing the recursive depth of the framework.
Learning Objectives
- Define a functor and verify the functor laws: preservation of identity and composition.
- Identify graph homomorphisms as functors between graph-categories.
- Define natural transformations and draw and interpret the naturality square.
- Explain polymorphic functions as natural transformations between functors on types.
- Construct the functor category [C, D] and verify it satisfies the category axioms.
- Apply the definitions to recognize functors and natural transformations in database migration and type systems.
Materials
Key Concepts
- Functor: A structure-preserving map F: C → D between categories; maps objects to objects and morphisms to morphisms while preserving composition and identity.
- Functor Laws: F(id_c) = id_{F(c)} and F(g ∘ f) = F(g) ∘ F(f); a functor respects the algebraic structure of the source category.
- Natural Transformation: A family of morphisms η_c: F(c) → G(c) indexed by objects c ∈ C, satisfying the naturality condition that all naturality squares commute.
- Naturality Square: For each morphism f: c → d, the square η_d ∘ F(f) = G(f) ∘ η_c must commute; naturality expresses coherent behavior across the whole category.
- Functor Category: The category [C, D] whose objects are functors C → D and whose morphisms are natural transformations; the category of all structure-preserving maps between two categories.
- Contravariant Functor: A functor F: C^op → D that reverses the direction of morphisms; arises naturally in the hom-functor construction.
Central Concepts from Prerequisites
- Module 2: categories, objects, morphisms, composition
- Functional programming: higher-order functions, parametric polymorphism
- Type theory: type constructors as functors (helpful)