Category Theory: Functors, Monads & FP

Learning Goal: Understand category theory's core elements—including categories, functors, natural transformations, and monads—and master their practical application to functional programming paradigms (e.g., in Haskell and Scala).

Prerequisites

  • Basic familiarity with programming logic (e.g., writing simple functions, arrays/lists, and type structures).
  • No prior advanced mathematics or set theory required.

Estimated Total Study Time

  • 12 Hours (including video lectures, practical code reflection, and self-assessments).

Module 1: Mathematical Foundations: Functions, Composition & Types

To build a solid category-theoretical intuition, we must first look at the mathematical building blocks that programmers use daily: functions, sets, and types. This module bridges the gap between the concrete sets of mathematics and the type systems of modern programming languages.

Recommended Videos

Introduction to Function Composition
Introduction to Function Composition
@ProfAllisonKraft00:421,625
Introduction to Function Composition

Function composition can be understood through an assembly line analogy: two functions act on an original X value in sequence. One person receives a piece of metal and bends it into a certain shape, then passes it to the next person who paints it, and so on. Each function transforms the input, and the output of one function becomes the input for the next function, creating a chain of transformations.

@ProfAllisonKraft · 00:42

Why this video

This brief animation introduces function composition through the intuitive analogy of an assembly line. This visual model establishes the foundational pipeline model used in category-theoretic morphisms.

Scott Wlaschin — Railway oriented programming
Scott Wlaschin — Railway oriented programming
@TechTrainFest03:3016,891
Scott Wlaschin — Railway oriented programming

In statically typed functional programming languages like F#, OCaml, Haskell, or Elm, types are fundamentally different from object-oriented classes. Types represent sets of values (like the set of all integers or all strings) rather than objects with behavior. A type is simply a name given to a collection of possible values. For example, 'fruit' is the set of all possible fruits, and 'fruit arrow fruit' represents the set of all functions that take a fruit and return a fruit. This set-based vie

@TechTrainFest · 03:30

Why this video

Scott Wlaschin explains how types operate as sets of values (e.g., the set of all integers, strings, or booleans) in statically typed functional programming. Understanding "types as sets" is vital because Category Theory's most common computer science model (Ask\mathbf{Ask}) represents types as objects and pure functions as morphisms.

A Taste of Type Theory • Bartosz Milewski • YOW! 2019
A Taste of Type Theory • Bartosz Milewski • YOW! 2019
@GOTO-03:3111,834
A Taste of Type Theory • Bartosz Milewski • YOW! 2019

Type theory serves as the foundation of mathematics while simultaneously being a practical tool in programming. It represents a convergence point between mathematical foundations and computer science. While some programming languages like JavaScript minimize type usage, typed languages leverage types for correctness. The journey from programming to type theory involves understanding recursive types, dependent types, induction principles, and ultimately identity types. This progression reveals ho

@GOTO- · 03:31

Why this video

Bartosz Milewski explains how type theory forms the bedrock of both computer science and modern mathematics. This addresses the curriculum feedback gap by demonstrating how types act as propositions, showing that programming types are more than compiler checkers—they are mathematical structures.

Python Video 05a: Functions and Lambda Functions
Python Video 05a: Functions and Lambda Functions
@carrollmath514100:42404
Python Video 05a: Functions and Lambda Functions

A function in mathematics is a tool where you input something, perform an operation on it, and get something out. In computer programming, a function follows the same concept: you input a collection of things, apply code to them, and get a result. This fundamental concept applies across both mathematical and programming contexts.

@carrollmath5141 · 00:42

Why this video

A quick programming-focused definition that grounds mathematical maps in the syntax of computer functions and lambdas. This ensures you understand that a function in programming is simply a tool that takes an input type and yields an output type.

Knowledge Checkpoint

  • What is the set-theoretic definition of a function, and how does a type in programming act as a set of possible values?
  • If you compose function f:A→Bf: A \to B with function g:B→Cg: B \to C, what is the signature of the resulting function g∘fg \circ f?
  • How does Russell's paradox highlight the transition from untyped set theory to structured type theory?

Module 2: Introduction to Category Theory: Objects & Morphisms

This module introduces the formal definition of a Category. You will study structural diagrams, nodes (objects), arrows (morphisms), identity, and composition rules—leaving behind implementation details to view computation as a web of relationships.

Recommended Videos

A Sensible Introduction to Category Theory
A Sensible Introduction to Category Theory
@OliverLugg03:26524,824
A Sensible Introduction to Category Theory

Categories can be visualized using diagrams where objects are nodes and morphisms are arrows. Composition corresponds to joining arrows nose-to-tail, and associativity allows writing compositions without parentheses. A diagram commutes if all paths between objects yield equal morphisms, efficiently encoding multiple equations simultaneously. An isomorphism is a morphism with an inverse, meaning two objects are functionally identical within their category. In Set, isomorphic sets have the same ca

@OliverLugg · 03:26

Why this video

This visual introduction translates category-theoretical diagrams into intuitive geometries. It shows how objects are points and morphisms are arrows, demonstrating how the fundamental laws of composition and associativity work visually.

Category Theory 1.1: Motivation and Philosophy
Category Theory 1.1: Motivation and Philosophy
@DrBartosz46:46375,853
Category Theory 1.1: Motivation and Philosophy

Category theory provides a high-level mathematical framework that unifies seemingly distinct areas of mathematics (geometry, algebra, topology, set theory, type theory, and logic) by revealing they share the same underlying structure at sufficiently high levels of abstraction, and it serves as a powerful tool for programmers to reason about complex systems by decomposing problems into smaller, composable components that can be abstracted and reused across different domains.

@DrBartosz · 46:46

Why this video

Bartosz Milewski's landmark lecture details why Category Theory is crucial for software engineering. He frames the subject not as dry math, but as the ultimate "science of composition" that helps us manage software complexity by abstracting details away.

Category Theory 1.2: What is a category?
Category Theory 1.2: What is a category?
@DrBartosz10:55281,406
Category Theory 1.2: What is a category?

Category theory rests on three core concepts: abstraction, composition, and identity. Abstraction involves removing unnecessary details so that seemingly different things become identical. Composition allows combining arrows between objects, while identity provides neutral elements in composition. Categories consist of objects and arrows (morphisms), but are not necessarily sets—using 'bunch' avoids set-theoretic paradoxes like the Barber's Paradox. Both objects and morphisms are primitive conce

@DrBartosz · 10:55

Why this video

Following his motivational introduction, Milewski defines a category mathematically. He covers the three pillars: abstraction, composition, and identity, providing the foundation needed to understand functors and natural transformations.

Programming with Categories - Lecture 1
Programming with Categories - Lecture 1
@ToposInstitute50:28283,111
Programming with Categories - Lecture 1

Category theory provides a foundational framework for mathematics and programming by abstracting away implementation details to focus on relationships between structures; a category consists of objects and morphisms (functions) between them, governed by two fundamental laws: associativity of composition (f ∘ (g ∘ h) = (f ∘ g) ∘ h) and the existence of identity morphisms (f ∘ id = f and id ∘ f = f), enabling powerful abstractions like isomorphisms that capture structural equivalence between diffe

@ToposInstitute · 50:28

Why this video

This lecture from the Topos Institute focuses on Category Theory's role as an interface specification language for programmers. It defines objects as types and morphisms as functions, introducing the structural rules that make software systems modular and testable.

Knowledge Checkpoint

  • What are the formal components that define a Category?
  • Explain the identity law: if f:A→Bf: A \to B, what is the result of f∘idAf \circ \text{id}_A and idB∘f\text{id}_B \circ f?
  • Explain the associative property of morphism composition using three arrows (ff, gg, and hh).

Module 3: Functors: Mapping Between Categories

Now that you understand categories, you can explore how to link them. A Functor is a structure-preserving map from one category to another. In programming, a functor takes a type and wraps it in a context (like List, Option, or Future), while allowing you to map functions over that wrapped value via map or fmap.

Recommended Videos

Category Theory 6.1: Functors
Category Theory 6.1: Functors
@DrBartosz54:1064,053
Category Theory 6.1: Functors

A functor is a mapping between categories that preserves the structure of objects and morphisms, including composition and identity; in programming, functors are implemented as type constructors paired with a function (often called fmap) that lifts functions over the contents of the container while maintaining the container's structure, with common examples including the Maybe type (which handles optional values) and its fmap implementation that applies functions to Just values while returning N

@DrBartosz · 54:10

Why this video

This lecture connects the abstract mathematical definitions of functors to type constructors. Milewski demonstrates how functors translate both objects (types) and morphisms (functions) from a source category to a target category.

What the Functor? \| Functors in Scala \| Rock the JVM
What the Functor? \| Functors in Scala \| Rock the JVM
@rockthejvm24:4213,697
What the Functor? \| Functors in Scala \| Rock the JVM

A functor is a type class that generalizes the map transformation concept across different data structures, allowing a single API to transform any mappable container (like lists, options, tries, or custom trees) without code duplication by providing a uniform map method that transforms values while preserving the container's structure.

@rockthejvm · 24:42

Why this video

This video explains how the theoretical definition of a functor is implemented in production-grade Scala. It shows how the Functor type class generalizes structural map patterns across different structures like Lists, Options, and Try blocks.

Haskell: Functors
Haskell: Functors
@scrilla10309:2816,822
Haskell: Functors

A Functor in Haskell is a type class that defines a function fmap with the type signature (a -> b) -> F a -> F b, which generalizes the map function to work on any data structure; it takes a function and a container (like a list or tree) and applies that function to every element inside, returning a new container with the transformed elements, enabling consistent element-wise operations across different data structures.

@scrilla103 · 09:28

Why this video

This tutorial focuses on Haskell's type signature for functors, showing how fmap :: (a -> b) -> f a -> f b lifts a standard function to operate within a context ff.

Knowledge Checkpoint

  • What does a functor do to the objects of a category? What does it do to the morphisms?
  • What are the two functor laws (Identity and Composition preservation)? Why must a valid programmer-defined map obey them?
  • Write down the type signature of fmap in Haskell or Scala, and explain the concept of "lifting" a function.

Module 4: Natural Transformations: Mapping Between Functors

If functors are mappings between categories, Natural Transformations are mappings between functors. They allow you to transform one functor structural context to another (e.g., converting a List to an Option or a Validation type) without modifying or inspecting the underlying payload types.

Recommended Videos

Category Theory 9.1: Natural transformations
Category Theory 9.1: Natural transformations
@DrBartosz12:3437,661
Category Theory 9.1: Natural transformations

Category theory rests on three foundational pillars: (1) Categories define what structure means, (2) Functors are mappings between categories that embed one category inside another to search for patterns or model categories, and (3) Natural transformations are the most important concept as they enable comparison between different functors. A natural transformation between functors F and G consists of a family of morphisms, one for each object, satisfying the naturality square condition: α_B ∘ Ff

@DrBartosz · 12:34

Why this video

Milewski explains the transition from functors to natural transformations, framing them as the "third pillar" of Category Theory. This lecture uses intuitive structural visualizations to show how natural transformations act as bridges between different functors.

Natural transformations 1
Natural transformations 1
@TheCatsters09:3719,779
Natural transformations 1

A natural transformation between two functors F and G from category C to category D is defined by a collection of morphisms α_X: F(X) → G(X) for each object X in C, such that for every morphism f: X → Y in C, the naturality square commutes, meaning that applying α_Y after F(f) equals applying G(f) after α_X; this definition can be understood through an analogy with homotopy, where a natural transformation corresponds to a continuous deformation between maps, and can be viewed as a functor from t

@TheCatsters · 09:37

Why this video

This classic, chalkboard-style presentation details the formal commuting square definition of a natural transformation. It is excellent for learners seeking mathematical rigor.

Profunctor Optics: The Categorical Approach - Bartosz Milewski
Profunctor Optics: The Categorical Approach - Bartosz Milewski
@LambdaWorld05:2014,850
Profunctor Optics: The Categorical Approach - Bartosz Milewski

Functors map objects and arrows between categories; natural transformations provide polymorphic mappings between functors. The Yoneda lemma establishes that polymorphic higher-order functions are equivalent to direct data values. This foundational result enables switching between function-based and data-based representations, crucial for optimizing and composing complex systems.

@LambdaWorld · 05:20

Why this video

This segment links the abstract commuting diagrams to polymorphic higher-order programming. It details how parametric polymorphism ensures that a natural transformation cannot alter the data values inside a container, preserving the structures of both functors.

Curriculum Gap Note: In practical code, a natural transformation is a polymorphic function with a signature like alpha :: forall a. F a -> G a (where F and G are Functors).

A common example is a safe headOption function converting List a -> Option a:

def headOption[A](xs: List[A]): Option[A] = xs.headOption

To satisfy the naturality condition, mapping a function ff over the list first and then applying headOption must yield the same result as applying headOption first and then mapping ff over the option: headOption(xs.map(f))≡headOption(xs).map(f)\text{headOption}(xs.\text{map}(f)) \equiv \text{headOption}(xs).\text{map}(f)

Knowledge Checkpoint

  • Define a natural transformation mathematically. What must commute in its diagram?
  • How does a polymorphic function signature (like forall a. F a -> G a) map to the definition of a natural transformation?
  • Verify the naturality condition using List and Option with a simple mapping function, such as x => x * 2.

Module 5: Monads: Structure and Applications in FP

We now arrive at the central abstraction of functional programming: the Monad. You will learn how to demystify Monads as endofunctors with additional structure, unpack the famous "monoids in the category of endofunctors" definition, and explore how they manage computational effects, state, and errors.

Recommended Videos

What is a Monad? - Computerphile
What is a Monad? - Computerphile
@Computerphile21:49646,960
What is a Monad? - Computerphile

A monad is a programming construct that provides a unified framework for handling computational effects (such as failure, input/output, mutable state, and non-determinism) in a pure functional language like Haskell. It consists of three core components: a type constructor (like Maybe), a return function that lifts pure values into the monadic context, and a sequencing operator (>>=) that chains operations while automatically managing effects. By abstracting away the boilerplate code needed to ha

@Computerphile · 21:49

Why this video

This presentation explains monads using practical functional programming examples. It details how the Monad abstraction solves real-world engineering issues, such as error propagation, side effects, and state modification in pure functional languages.

The Functional Programmer's Toolkit - Scott Wlaschin
The Functional Programmer's Toolkit - Scott Wlaschin
@NDC01:2276,822
The Functional Programmer's Toolkit - Scott Wlaschin

A monad is an effect type plus two functions (return/pure/unit and bind) plus rules (laws) that implementations must follow. The return function lifts values into the effect world; the bind function converts diagonal functions into horizontal ones. Monad laws ensure consistent behavior: left identity (return x >>= f ≡ f x), right identity (m >>= return ≡ m), and associativity ((m >>= f) >>= g) ≡ (m >>= (λx → f x >>= g)). Breaking these laws causes unexpected behavior.

@NDC · 01:22

Why this video

This excerpt details how monads consist of an effect type wrapped with two operations: return (also known as pure or unit) and bind (or flatMap). It explains how these two operations let you safely chain dependent, effectful actions.

Haskell for Imperative Programmers #17 - Monads
Haskell for Imperative Programmers #17 - Monads
@philipphagenlocher14:4375,496
Haskell for Imperative Programmers #17 - Monads

Monads in Haskell are computational structures that handle context and side effects through three core functions: return (wraps a value into a monad), bind (>>=) (extracts the internal value and applies a function, propagating errors), and the anonymous bind (>>) (ignores the result while propagating errors). The bind operator enables chaining monadic operations while handling errors gracefully, as demonstrated with Maybe types where Nothing propagates through computations. Monads must satisfy t

@philipphagenlocher · 14:43

Why this video

This programming tutorial explains how to transition from imperative sequencing to monadic composition. It provides step-by-step Haskell examples of the bind operator (>>=) and Haskell's syntactic sugar, do notation.

Functional programming design patterns by Scott Wlaschin
Functional programming design patterns by Scott Wlaschin
@ivanplyusnin329203:07199,072
Functional programming design patterns by Scott Wlaschin

Monads can be understood as monoids in the category of endofunctors. Both share the same fundamental structure: closure, associativity, and identity. The monad laws are essentially monoid laws expressed in terms of functor composition. This categorical perspective reveals deep connections between seemingly different concepts. Understanding this relationship provides profound insights into functional programming's theoretical foundations and unifies diverse patterns under a common mathematical fr

@ivanplyusnin3292 · 03:07

Why this video

This video explains the famous quote: "A monad is a monoid in the category of endofunctors." It demonstrates how monad operations correspond to the monoid properties of closure, identity, and associativity.

Knowledge Checkpoint

  • What are the two primary operations that define a Monad, and what are their typical type signatures (flatMap / bind and unit / pure)?
  • Explain how a Monad serves as a "monoid in the category of endofunctors" by identifying its identity element and binary operator.
  • How does the Maybe (or Option) monad prevent deeply nested conditional blocks when handling potentially null values?

Course Map

This flowchart shows the recommended learning path and structural dependencies of the modules:

Key People Index

  • Bartosz Milewski: A leading computer scientist and physicist who bridges the gap between category theory and programming. His educational lectures are standard resources for functional programming.
  • Scott Wlaschin: Author and functional programming advocate known for "Railway Oriented Programming," which translates algebraic concepts into practical patterns for enterprise developers.
  • Saunders Mac Lane & Samuel Eilenberg: The mathematicians who co-founded Category Theory in the 1940s while working in algebraic topology.
  • Eugenio Moggi: The computer scientist who first proposed using monads to structure functional programs and handle side effects in 1989.

Final Self-Assessment

Review this checklist to assess your understanding of the course material:

  • Morphisms: Can you explain the difference between an object and a morphism, and draw a commuting diagram for g∘fg \circ f?
  • Category Laws: Can you list the formal requirements of a category (identity and associativity)?
  • Types as Objects: Can you explain how the category of types (Ask\mathbf{Ask}) uses types as objects and pure functions as morphisms?
  • Functor Lifting: Can you explain how map (or fmap) lifts a function A→BA \to B to a function F(A)→F(B)F(A) \to F(B)?
  • Functor Laws: Can you explain what happens if a functor violates the identity law?
  • Natural Transformations: Can you define a natural transformation as a family of morphisms that maps one functor to another?
  • Naturality Property: Can you explain why a natural transformation cannot inspect or alter the generic type parameter of a container?
  • Monadic Bind: Can you explain why flatMap (or bind) is needed to chain monadic functions, instead of just using map?
  • Monad Laws: Can you write out the three monad laws (Left Identity, Right Identity, and Associativity)?
  • Monoids & Monads: Can you explain how the monad operations of pure and join function as the identity and multiplication operations of a monoid?
Explore Further

Related Mathematics Roadmaps

View All→
mathematics

Non-Euclidean Geometry: Models & Geodesics

01Euclid's Fifth Postulate and the Birth of New Geometries
02Hyperbolic Space and the Poincaré Disk Model
03Geodesics: Defining Straight Lines in Curved Spaces
+ 2 more learning modules
15h5 modules
Explore Roadmap
mathematics

Knot Theory — Moves, Coloring & Polynomials

01Introduction to Topology and Knots
02Reidemeister Moves & Knot Equivalence
03Knot Invariants and Tricolorability
+ 2 more learning modules
12h5 modules
Explore Roadmap
mathematics

Complex Analysis: Residues & Contour Integrals

01Foundations of Complex Numbers
02Complex Functions and Holomorphic Properties
03Complex Integration and Cauchy's Theorem
+ 2 more learning modules
18h5 modules
Explore Roadmap
mathematics

Numerical Analysis: Roots, Splines & Errors

01Computer Arithmetic and Error Analysis
02Root-Finding Methods
03Polynomial Interpolation & Runge's Phenomenon
+ 2 more learning modules
18h5 modules
Explore Roadmap