Introduction to categories

What is Category Theory?

Category theory is a branch of mathematics that studies abstract structures and relationships between them. Rather than focusing on what objects are made of, category theory emphasizes how objects relate to each other through morphisms (structure-preserving maps).

In programming, category theory provides a formal framework for understanding composition, abstraction, and generic patterns that appear across different data types and programming paradigms.

Definition of a Category

A category $\mathcal{C}$ consists of:

A collection of objects (denoted $A, B, C, …$)
A collection of morphisms (also called arrows or maps) between objects
For each object $A$, an identity morphism $\text{id}_A : A \to A$
A composition operation that combines morphisms

These components must satisfy two axioms:

Associativity

For morphisms $f : A \to B$, $g : B \to C$, and $h : C \to D$:

\[h \circ (g \circ f) = (h \circ g) \circ f\]

Identity Laws

For any morphism $f : A \to B$:

\[\text{id}_B \circ f = f = f \circ \text{id}_A\]

Basic Examples

1. The Category Set

Objects: Sets ($\mathbb{R}$, $\mathbb{Z}$, etc.)
Morphisms: Functions between sets
Identity: The identity function $\text{id}_A(x) = x$
Composition: Standard function composition $(g \circ f)(x) = g(f(x))$

2. The Category Vect

Objects: Vector spaces
Morphisms: Linear transformations
Identity: The identity transformation
Composition: Composition of linear maps

3. Categories in Programming

The Category Hask (Haskell types):

Objects: Haskell types (Int, String, [a], etc.)
Morphisms: Functions between types
Identity: id :: a -> a defined as id x = x
Composition: Function composition (.) :: (b -> c) -> (a -> b) -> (a -> c)

-- Identity function
id :: a -> a
id x = x

-- Function composition
(.) :: (b -> c) -> (a -> b) -> (a -> c)
(g . f) x = g (f x)

4. The Category Poset

Any partially ordered set $(P, \leq)$ forms a category:

Objects: Elements of $P$
Morphisms: There exists a unique morphism $a \to b$ if and only if $a \leq b$
Identity: Reflexivity ($a \leq a$)
Composition: Transitivity ($a \leq b$ and $b \leq c$ implies $a \leq c$)

Morphisms in Detail

A morphism $f : A \to B$ in a category $\mathcal{C}$ is written with:

Domain: Object $A$ (the source)
Codomain: Object $B$ (the target)

Special Types of Morphisms

Isomorphism: A morphism $f : A \to B$ is an isomorphism if there exists $g : B \to A$ such that: $g \circ f = \text{id}_A \quad \text{and} \quad f \circ g = \text{id}_B$
Monomorphism: A morphism $f : A \to B$ is a monomorphism if for all morphisms $g, h : C \to A$: $f \circ g = f \circ h \implies g = h$ (Generalizes injectivity)
Epimorphism: A morphism $f : A \to B$ is an epimorphism if for all morphisms $g, h : B \to C$: $g \circ f = h \circ f \implies g = h$ (Generalizes surjectivity)
Endomorphism: A morphism $f : A \to A$ from an object to itself

String Diagrams and Graphical Calculus

Category theory can be visualized using string diagrams, a graphical notation where:

Objects are represented as wires (strings)
Morphisms are represented as boxes with input and output wires
Composition is represented by connecting wires vertically
Identity morphisms are represented as straight wires

The Identity Cap and Discard Cap

In monoidal categories (categories with a tensor product), we have special morphisms called caps and cups:

Identity Cap (or Cup)

The identity cap (or cup) is a morphism $\eta : I \to A \otimes A^*$ where:

$I$ is the monoidal unit
$A^*$ is the dual of object $A$
Graphically represented as a ∩-shaped curve connecting two wires

In string diagram notation (cup/creation map):

This represents the “creation” of a pair of objects from nothing (the monoidal unit).

Discard Cap (or Cap)

The discard cap (or simply cap) is a morphism $\epsilon : A^* \otimes A \to I$ where:

Graphically represented as an inverted cup connecting two wires from above

In string diagram notation (cap/evaluation map):

This represents the “annihilation” or “evaluation” of a pair of dual objects.

Zigzag Identity

Together, the cup and cap satisfy the zigzag equations (also called snake equations):

\[(\text{id}_A \otimes \epsilon) \circ (\eta \otimes \text{id}_A) = \text{id}_A\] \[(\epsilon \otimes \text{id}_{A^*}) \circ (\text{id}_{A^*} \otimes \eta) = \text{id}_{A^*}\]

Graphically, the zigzag composition:

simplifies to a straight wire (identity).

Connection to Programming

1. Types as Objects, Functions as Morphisms

In functional programming, we work in a category where:

Types are objects
Pure functions are morphisms
Function composition is categorical composition

-- Types as objects
type A = Int
type B = String
type C = Bool

-- Functions as morphisms
f :: A -> B
f = show

g :: B -> C
g = null

-- Composition
h :: A -> C
h = g . f

2. Identity and Composition Laws

Programming languages that support higher-order functions naturally express categorical structure:

-- Identity laws
id . f == f
f . id == f

-- Associativity
h . (g . f) == (h . g) . f

3. Polymorphic Functions as Natural Transformations

A polymorphic function like length or head works uniformly across different types:

length :: [a] -> Int
-- Works for any type a

head :: [a] -> a
-- Preserves the type

These are examples of natural transformations between functors.

4. Functors: Mapping Between Categories

A functor $F : \mathcal{C} \to \mathcal{D}$ maps:

Objects in $\mathcal{C}$ to objects in $\mathcal{D}$
Morphisms in $\mathcal{C}$ to morphisms in $\mathcal{D}$

Functors must preserve composition and identity:

$F(g \circ f) = F(g) \circ F(f)$ $F(\text{id}_A) = \text{id}_{F(A)}$

In programming, type constructors like List, Maybe, Either are functors:

class Functor f where
  fmap :: (a -> b) -> f a -> f b

-- List functor
instance Functor [] where
  fmap = map

-- Maybe functor
instance Functor Maybe where
  fmap f Nothing  = Nothing
  fmap f (Just x) = Just (f x)

5. Monads: A Special Kind of Functor

A monad is a functor with additional structure:

class Monad m where
  return :: a -> m a           -- Unit
  (>>=)  :: m a -> (a -> m b) -> m b  -- Bind

The monad laws correspond to categorical axioms:

-- Left identity
return a >>= f  ==  f a

-- Right identity
m >>= return  ==  m

-- Associativity
(m >>= f) >>= g  ==  m >>= (\x -> f x >>= g)

Examples in programming:

Maybe monad: Handles computations that may fail
List monad: Handles non-deterministic computations
IO monad: Handles side effects in a pure functional language

6. Caps and Discard in Programming

The cap and discard concepts appear in programming through:

Creation (Identity Cap/Cup)

Creating values from unit/context:

-- Creating a pair from unit
createPair :: () -> (a, a)
createPair () = (x, x) where x = someValue

-- In monads, 'return' acts like a cup
return :: a -> m a

Evaluation/Discard (Discard Cap)

Combining or evaluating pairs:

-- Evaluating/applying a function to an argument
apply :: (a -> b, a) -> b
apply (f, x) = f x

-- Discarding information
const :: a -> b -> a
const x _ = x

-- In monads, 'join' collapses nested structure
join :: m (m a) -> m a

The zigzag identity in programming corresponds to laws like:

-- For monads
join . return == id
join . fmap return == id

Properties and Theorems

Uniqueness of Identity

In any category, the identity morphism $\text{id}_A$ for an object $A$ is unique.

Proof: Suppose $e$ and $e’$ are both identity morphisms for $A$. Then: $e = e \circ e' = e'$

where the first equality uses $e’$ as identity and the second uses $e$ as identity.

Uniqueness of Composition

For morphisms $f : A \to B$ and $g : B \to C$, the composition $g \circ f$ is unique.

Isomorphisms are Invertible

If $f : A \to B$ is an isomorphism with inverse $g : B \to A$, then $g$ is also an isomorphism with inverse $f$.

Categories in Different Programming Paradigms

Object-Oriented Programming

Even in OOP, categorical thinking appears:

Objects: Classes or interfaces
Morphisms: Methods that transform one object to another
Composition: Method chaining or the composite pattern

# Python example
class Functor:
    def fmap(self, f):
        raise NotImplementedError

class List(Functor):
    def __init__(self, items):
        self.items = items

    def fmap(self, f):
        return List([f(x) for x in self.items])

# Composition
result = some_list.fmap(f).fmap(g)

Imperative Programming

State transformations can be viewed categorically:

Objects: Program states
Morphisms: State transitions (commands)
Composition: Sequential execution

Common Patterns from Category Theory in Programming

Pipeline/Composition: Unix pipes, method chaining

cat file.txt | grep "pattern" | sort | uniq

Map/Filter/Reduce: Operations on collections preserve categorical structure
```
arr.map(f).map(g) === arr.map(x => g(f(x)))
```
Dependency Injection: Objects and their relationships form a category
Reactive Programming: Streams and their transformations

Why Category Theory Matters for Programming

Abstraction: Identify common patterns across different domains
Composition: Build complex systems from simple, composable parts
Reasoning: Use mathematical laws to reason about program behavior
Genericity: Write code that works for many types (parametric polymorphism)
Correctness: Formal properties help ensure program correctness

Exercises

Verify that function composition in your favorite programming language satisfies associativity and the identity laws.
Prove that in the category Set, if $f : A \to B$ and $g : B \to A$ satisfy $g \circ f = \text{id}_A$ and $f \circ g = \text{id}_B$, then $f$ is bijective.
Consider the category where objects are types in a programming language and morphisms are subtype relationships. Is this a valid category? Why or why not?
Implement a Functor instance for a binary tree data structure in your language of choice. Verify that it satisfies the functor laws:
- fmap id == id
- fmap (g . f) == fmap g . fmap f
Show that the monoid of endomorphisms $\text{End}(A) = {f : A \to A}$ under composition forms a category with a single object.
Given morphisms $f : A \to B$ and $g : B \to C$ in a category, show that if both $f$ and $g$ are isomorphisms, then $g \circ f$ is also an isomorphism.
In the category Poset (partially ordered sets), what do products and coproducts correspond to? (Hint: think about meets and joins)
Write a function in Haskell or another functional language that demonstrates the zigzag identity for the State monad.
Consider the Maybe functor:
```
fmap :: (a -> b) -> Maybe a -> Maybe b
```
Prove that this satisfies the functor laws by considering both the Nothing and Just x cases.
Implement function composition as an operator in your programming language and verify the associativity property with test cases.
String Diagram Exercise: Draw the string diagram for the composition of three morphisms $f : A \to B$, $g : B \to C$, and $h : C \to D$, showing that $(h \circ g) \circ f = h \circ (g \circ f)$.
Programming Exercise: Create a Category type class in a language of your choice that captures the essential structure of a category. Implement instances for at least two different categories.

See: