Notes on Category Theory for Programmers

A practical introduction to functors, monads, and natural transformations through the lens of everyday code.

mathematicsfunctional-programmingcategory-theory

Why Category Theory?

Category theory provides a language for describing patterns that appear across different areas of mathematics and computer science. For programmers, it offers:

  • A vocabulary for design patterns that transcend specific languages
  • Tools for reasoning about composition
  • A framework for understanding type system features
Prerequisites

You don’t need a math degree. If you understand function composition and generic types, you’re ready.

Categories

A category consists of:

  1. Objects — think of these as types
  2. Morphisms (arrows) — think of these as functions between types
  3. Composition — if f:A→Bf: A \to B and g:B→Cg: B \to C, then g∘f:A→Cg \circ f: A \to C
  4. Identity — for every object AA, there exists idA:A→Aid_A: A \to A
graph LR A((A)) -->|f| B((B)) B -->|g| C((C)) A -->|"g ∘ f"| C A -->|id_A| A

Functors

A functor is a structure-preserving map between categories. In programming, this is exactly the map operation:

// Array is a functor
[1, 2, 3].map(x => x * 2)  // [2, 4, 6]

// Option/Maybe is a functor
Some(5).map(x => x * 2)     // Some(10)
None.map(x => x * 2)        // None

// Promise is a functor
fetch(url).then(r => r.json())  // Promise<Response> → Promise<JSON>

The functor laws express that map preserves structure:

map(id)=id(identity)\text{map}(id) = id \quad \text{(identity)} map(g∘f)=map(g)∘map(f)(composition)\text{map}(g \circ f) = \text{map}(g) \circ \text{map}(f) \quad \text{(composition)}

Monads

A monad is a functor with two additional operations:

  • unit (also called return or pure): wraps a value — A→M(A)A \to M(A)
  • flatMap (also called bind or >>=): chains operations — M(A)→(A→M(B))→M(B)M(A) \to (A \to M(B)) \to M(B)
// Promise monad
const getUser = (id: string): Promise<User> => fetch(`/users/${id}`).then(r => r.json());
const getPosts = (user: User): Promise<Post[]> => fetch(`/posts?author=${user.id}`).then(r => r.json());

// flatMap chains dependent async operations
getUser("123")
  .then(user => getPosts(user))
  .then(posts => console.log(posts));
The key insight

Monads let you sequence computations that produce wrapped values, handling the wrapping/unwrapping automatically. This is why they’re useful for effects: async, errors, state, I/O.

Natural Transformations

A natural transformation converts between functors while preserving structure. In code:

// Array → Option (head)
function head<T>(arr: T[]): Option<T> {
  return arr.length > 0 ? Some(arr[0]) : None;
}

// Option → Array
function toArray<T>(opt: Option<T>): T[] {
  return opt.isSome() ? [opt.value] : [];
}

The naturality condition states that it doesn’t matter whether you transform first and then map, or map first and then transform:

ηB∘F(f)=G(f)∘ηA\eta_B \circ F(f) = G(f) \circ \eta_A

This is what makes generic library code reliable — natural transformations guarantee consistent behavior regardless of the contained type.

#category-theory #functional-programming #mathematics #type-theory