Category Theory

MathPhysCS CodeLab on Category Theory

Mathematical Logic

Category Theory

Author

Rong-Kang Zhang

Published

November 23, 2025

Keywords

Natural Transformation, Functor, Adjoint Functor, Limits, Programming

1 Category Theory: Programming Perspective

1.1 Introduction

This document explores category theory from a computational and programming perspective. While category theory is a branch of mathematics, its abstract nature makes it highly relevant to computer science, particularly in the design of programming languages, type systems, and software architectures.

In this CodeLab, we will:

Implement core categorical concepts in programming languages
Explore how category theory influences functional programming
Apply categorical patterns to solve computational problems
Use visualization tools to understand categorical structures

1.2 1. Foundational Definitions

1.2.1 1.1 Categories

Definition 1 A category $\mathcal{C}$ consists of: 1. A collection of objects $\text{ob}(\mathcal{C})$ 2. For every pair of objects $A, B$, a set $\text{hom}_{\mathcal{C}}(A, B)$ of morphisms (or arrows) from $A$ to $B$ 3. A composition operation $\circ$ that takes morphisms $f: A \to B$ and $g: B \to C$ and produces a morphism $g \circ f: A \to C$ 4. For each object $A$, an identity morphism $\text{id}_A: A \to A$

satisfying: - Associativity: $(h \circ g) \circ f = h \circ (g \circ f)$ - Identity: $f \circ \text{id}_A = f$ and $\text{id}_B \circ f = f$ for all $f: A \to B$

1.2.2 1.2 Programming with Categories

Let’s implement the concept of a category in Haskell:

-- Type class for categories
class Category cat where
    -- Identity morphism
    id :: cat a a
    -- Composition of morphisms
    (.) :: cat b c -> cat a b -> cat a c

-- Example: The category of Haskell functions
instance Category (->) where
    id x = x
    (g . f) x = g (f x)

In Python, we can represent categories using classes and objects:

from abc import ABC, abstractmethod
from typing import TypeVar, Generic, Callable

A = TypeVar('A')
B = TypeVar('B')
C = TypeVar('C')

class Morphism(ABC, Generic[A, B]):
    @abstractmethod
    def __call__(self, x: A) -> B:
        pass
    
    @abstractmethod
    def compose(self, other: 'Morphism[C, A]') -> 'Morphism[C, B]':
        pass

class FunctionMorphism(Morphism[A, B]):
    def __init__(self, func: Callable[[A], B]):
        self.func = func
    
    def __call__(self, x: A) -> B:
        return self.func(x)
    
    def compose(self, other: 'FunctionMorphism[C, A]') -> 'FunctionMorphism[C, B]':
        return FunctionMorphism(lambda x: self.func(other.func(x)))

# Identity morphism
def identity() -> FunctionMorphism[A, A]:
    return FunctionMorphism(lambda x: x)

1.3 2. Functors

1.3.1 2.1 Definition of Functors

Definition 2 A functor $F: \mathcal{C} \to \mathcal{D}$ between categories $\mathcal{C}$ and $\mathcal{D}$ consists of: 1. A mapping from objects of $\mathcal{C}$ to objects of $\mathcal{D}$: $A \mapsto F(A)$ 2. A mapping from morphisms of $\mathcal{C}$ to morphisms of $\mathcal{D}$: $f: A \to B \mapsto F(f): F(A) \to F(B)$

satisfying: - $F(\text{id}_A) = \text{id}_{F(A)}$ for all objects $A$ in $\mathcal{C}$ - $F(g \circ f) = F(g) \circ F(f)$ for all morphisms $f: A \to B$ and $g: B \to C$ in $\mathcal{C}$

1.3.2 2.2 Functors in Programming

In Haskell, the Functor type class represents endofunctors on the category of Haskell types:

class Functor f where
    fmap :: (a -> b) -> f a -> f b
    
    -- Laws:
    -- fmap id = id
    -- fmap (g . f) = fmap g . fmap f

-- Example: Maybe functor
data Maybe a = Nothing | Just a

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

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

In Python, we can implement functors using generic classes:

from typing import TypeVar, Generic, List, Optional, Callable

A = TypeVar('A')
B = TypeVar('B')

class Functor(Generic[A]):
    @abstractmethod
    def fmap(self, func: Callable[[A], B]) -> 'Functor[B]':
        pass

class Maybe(Functor[A]):
    def __init__(self, value: Optional[A]):
        self.value = value
    
    def fmap(self, func: Callable[[A], B]) -> 'Maybe[B]':
        if self.value is None:
            return Maybe(None)
        else:
            return Maybe(func(self.value))
    
    def __repr__(self):
        return f"Maybe({self.value})"

class List(Functor[A]):
    def __init__(self, values: List[A]):
        self.values = values
    
    def fmap(self, func: Callable[[A], B]) -> 'List[B]':
        return List([func(x) for x in self.values])
    
    def __repr__(self):
        return f"List({self.values})"

1.4 3. Natural Transformations

1.4.1 3.1 Definition of Natural Transformations

Definition 3 A natural transformation $\eta: F \Rightarrow G$ between functors $F, G: \mathcal{C} \to \mathcal{D}$ consists of: 1. For each object $A$ in $\mathcal{C}$, a morphism $\eta_A: F(A) \to G(A)$ in $\mathcal{D}$

such that for every morphism $f: A \to B$ in $\mathcal{C}$, the following diagram commutes:

\[\begin{CD} F(A) @>{\eta_A}>> G(A) \\ @V{F(f)}VV @VV{G(f)}V \\ F(B) @>{\eta_B}>> G(B) \end{CD}\]

i.e., $G(f) \circ \eta_A = \eta_B \circ F(f)$

1.4.2 3.2 Implementing Natural Transformations

In Haskell, natural transformations are represented as polymorphic functions:

-- A natural transformation from functor f to functor g
type NatTrans f g = forall a. f a -> g a

-- Example: Natural transformation from Maybe to List
maybeToList :: NatTrans Maybe []
maybeToList Nothing = []
maybeToList (Just x) = [x]

-- Example: Natural transformation from List to Maybe (taking the first element)
headMay :: NatTrans [] Maybe
headMay [] = Nothing
headMay (x:_) = Just x

In Python, we can implement natural transformations using generic functions:

from typing import TypeVar, Generic, Callable

F = TypeVar('F', bound=Functor)
G = TypeVar('G', bound=Functor)
A = TypeVar('A')

# A natural transformation is a generic function that transforms
# an object of functor F to an object of functor G
NaturalTransformation = Callable[[F[A]], G[A]]

# Example: Natural transformation from Maybe to List
def maybe_to_list(maybe: Maybe[A]) -> List[A]:
    if maybe.value is None:
        return List([])
    else:
        return List([maybe.value])

# Example: Natural transformation from List to Maybe (taking the first element)
def head_may(lst: List[A]) -> Maybe[A]:
    if not lst.values:
        return Maybe(None)
    else:
        return Maybe(lst.values[0])

1.5 4. Limits and Colimits

1.5.1 4.1 Product and Coproduct

Definition 4 The product of objects $A$ and $B$ in a category $\mathcal{C}$ is an object $A \times B$ together with projection morphisms $\pi_1: A \times B \to A$ and $\pi_2: A \times B \to B$ such that for any object $C$ and morphisms $f: C \to A$ and $g: C \to B$, there exists a unique morphism $\langle f, g \rangle: C \to A \times B$ making the following diagram commute:

\[\begin{CD} C @>{\langle f, g \rangle}>> A \times B \\ @V{f}VV @VV{\pi_1}V \\ A @= A \end{CD} \quad \begin{CD} C @>{\langle f, g \rangle}>> A \times B \\ @V{g}VV @VV{\pi_2}V \\ B @= B \end{CD}\]

Definition 5 The coproduct of objects $A$ and $B$ in a category $\mathcal{C}$ is an object $A + B$ together with injection morphisms $\iota_1: A \to A + B$ and $\iota_2: B \to A + B$ such that for any object $C$ and morphisms $f: A \to C$ and $g: B \to C$, there exists a unique morphism $[f, g]: A + B \to C$ making the following diagram commute:

\[\begin{CD} A @>{\iota_1}>> A + B \\ @V{f}VV @VV{[f, g]}V \\ C @= C \end{CD} \quad \begin{CD} B @>{\iota_2}>> A + B \\ @V{g}VV @VV{[f, g]}V \\ C @= C \end{CD}\]

1.5.2 4.2 Products and Coproducts in Programming

In Haskell, products are tuples and coproducts are Either:

-- Product: (a, b) is the product of a and b
-- Projections: fst and snd

fst :: (a, b) -> a
fst (x, _) = x

snd :: (a, b) -> b
snd (_, y) = y

-- Pairing function
pair :: (c -> a) -> (c -> b) -> c -> (a, b)
pair f g x = (f x, g x)

-- Coproduct: Either a b is the coproduct of a and b
data Either a b = Left a | Right b

-- Injections
left :: a -> Either a b
left = Left

right :: b -> Either a b
right = Right

-- Case analysis (cotupling)
caseEither :: (a -> c) -> (b -> c) -> Either a b -> c
caseEither f _ (Left x) = f x
caseEither _ g (Right y) = g y

In Python, we can implement products as tuples and coproducts as a custom Either class:

from typing import Tuple, TypeVar, Generic, Callable

A = TypeVar('A')
B = TypeVar('B')
C = TypeVar('C')

# Product: tuples are products in Python
# Projections
def fst(pair: Tuple[A, B]) -> A:
    return pair[0]

def snd(pair: Tuple[A, B]) -> B:
    return pair[1]

# Pairing function
def pair(f: Callable[[C], A], g: Callable[[C], B]) -> Callable[[C], Tuple[A, B]]:
    return lambda x: (f(x), g(x))

# Coproduct: Either type
class Either(Generic[A, B]):
    def __init__(self, is_left: bool, value: A | B):
        self.is_left = is_left
        self.value = value
    
    @staticmethod
    def left(value: A) -> 'Either[A, B]':
        return Either(True, value)
    
    @staticmethod
    def right(value: B) -> 'Either[A, B]':
        return Either(False, value)
    
    # Case analysis (cotupling)
    def case(self, f: Callable[[A], C], g: Callable[[B], C]) -> C:
        if self.is_left:
            return f(self.value)
        else:
            return g(self.value)

1.6 5. Adjoint Functors

1.6.1 5.1 Definition of Adjunctions

Definition 6 An adjunction between categories $\mathcal{C}$ and $\mathcal{D}$ consists of a pair of functors $F: \mathcal{D} \to \mathcal{C}$ (left adjoint) and $G: \mathcal{C} \to \mathcal{D}$ (right adjoint) together with a natural isomorphism:

\[\mathcal{C}(F(D), C) \cong \mathcal{D}(D, G(C))\]

for all objects $C$ in $\mathcal{C}$ and $D$ in $\mathcal{D}$.

1.6.2 5.2 Adjunctions in Programming

A classic example of adjunction in programming is the relationship between the Maybe type and the List type:

-- The "singleton" functor (left adjoint)
data Singleton a = Singleton a

instance Functor Singleton where
    fmap f (Singleton x) = Singleton (f x)

-- The "list" functor (right adjoint)
-- (List is already a Functor)

-- The adjunction between Singleton and List
unit :: a -> [a]
unit x = [x]

counit :: Singleton [a] -> a
counit (Singleton [x]) = x
counit _ = error "Counit defined only for singleton lists"

-- The natural transformations
leftAdjunct :: (Singleton a -> b) -> a -> [b]
leftAdjunct f x = [f (Singleton x)]

rightAdjunct :: (a -> [b]) -> Singleton a -> b
rightAdjunct f (Singleton x) = head (f x)  -- Partial function!

In Python, we can implement this adjunction as follows:

from typing import TypeVar, Generic, List, Callable

A = TypeVar('A')
B = TypeVar('B')

# The "singleton" functor (left adjoint)
class Singleton(Generic[A]):
    def __init__(self, value: A):
        self.value = value
    
    def fmap(self, func: Callable[[A], B]) -> 'Singleton[B]':
        return Singleton(func(self.value))

# The adjunction between Singleton and List
def unit(value: A) -> List[A]:
    return [value]

def counit(singleton: Singleton[List[A]]) -> A:
    # Note: This is a partial function
    if len(singleton.value) == 1:
        return singleton.value[0]
    else:
        raise ValueError("Counit defined only for singleton lists")

# The natural transformations
def left_adjunct(f: Callable[[Singleton[A]], B]) -> Callable[[A], List[B]]:
    return lambda x: [f(Singleton(x))]

def right_adjunct(f: Callable[[A], List[B]]) -> Callable[[Singleton[A]], B]:
    # Note: This is a partial function
    return lambda singleton: f(singleton.value)[0]

1.7 6. Monads

1.7.1 6.1 Definition of Monads

Definition 7 A monad on a category $\mathcal{C}$ is a triple $(T, \eta, \mu)$ consisting of: 1. An endofunctor $T: \mathcal{C} \to \mathcal{C}$ 2. A natural transformation $\eta: \text{id}_{\mathcal{C}} \Rightarrow T$ (unit) 3. A natural transformation $\mu: T \circ T \Rightarrow T$ (multiplication)

such that the following diagrams commute:

Associativity: \[\begin{CD} T(T(T(A))) @>{\mu_{T(A)}}>> T(T(A)) \\ @V{T(\mu_A)}VV @VV{\mu_A}V \\ T(T(A)) @>{\mu_A}>> T(A) \end{CD}\]
Unit laws: \[\begin{CD} T(A) @>{\eta_{T(A)}}>> T(T(A)) \\ @V{id_{T(A)}}VV @VV{\mu_A}V \\ T(A) @= T(A) \end{CD} \quad \begin{CD} T(A) @>{\mu_A}>> T(A) \\ @V{T(\eta_A)}VV @AA{id_{T(A)}}A \\ T(T(A)) @= T(A) \end{CD}\]

1.7.2 6.2 Monads in Programming

In Haskell, the Monad type class represents monads:

class Monad m where
    -- Unit: Inject a value into the monad
    return :: a -> m a
    
    -- Bind: Chain computations
    (>>=) :: m a -> (a -> m b) -> m b
    
    -- Multiplication (derivable)
    join :: m (m a) -> m a
    join x = x >>= id
    
    -- Laws:
    -- return a >>= f = f a
    -- m >>= return = m
    -- (m >>= f) >>= g = m >>= (\x -> f x >>= g)

-- Example: Maybe monad
instance Monad Maybe where
    return x = Just x
    
    Nothing >>= _ = Nothing
    Just x >>= f = f x

-- Example: List monad
instance Monad [] where
    return x = [x]
    
    xs >>= f = concat (map f xs)

In Python, we can implement monads using a generic class:

from typing import TypeVar, Generic, Callable, List, Optional

A = TypeVar('A')
B = TypeVar('B')

class Monad(Generic[A]):
    @abstractmethod
    def bind(self, func: Callable[[A], 'Monad[B]']) -> 'Monad[B]':
        pass
    
    @staticmethod
    @abstractmethod
    def return_(value: A) -> 'Monad[A]':
        pass
    
    def join(self) -> 'Monad[A]':
        # Default implementation for monads where join is bind with identity
        return self.bind(lambda x: x)

class MaybeMonad(Monad[A]):
    def __init__(self, value: Optional[A]):
        self.value = value
    
    def bind(self, func: Callable[[A], 'MaybeMonad[B]']) -> 'MaybeMonad[B]':
        if self.value is None:
            return MaybeMonad(None)
        else:
            return func(self.value)
    
    @staticmethod
    def return_(value: A) -> 'MaybeMonad[A]':
        return MaybeMonad(value)
    
    def __repr__(self):
        return f"MaybeMonad({self.value})"

class ListMonad(Monad[A]):
    def __init__(self, values: List[A]):
        self.values = values
    
    def bind(self, func: Callable[[A], 'ListMonad[B]']) -> 'ListMonad[B]':
        result = []
        for value in self.values:
            monad = func(value)
            result.extend(monad.values)
        return ListMonad(result)
    
    @staticmethod
    def return_(value: A) -> 'ListMonad[A]':
        return ListMonad([value])
    
    def __repr__(self):
        return f"ListMonad({self.values})"

1.8 7. Applications in Programming

1.8.1 7.1 Functional Programming Patterns

Category theory has heavily influenced functional programming. Here are some examples:

-- The State monad for managing stateful computations
newtype State s a = State { runState :: s -> (a, s) }

instance Functor (State s) where
    fmap f (State g) = State (\s -> let (a, s') = g s in (f a, s'))

instance Monad (State s) where
    return a = State (\s -> (a, s))
    State g >>= f = State (\s -> let (a, s') = g s in runState (f a) s')

-- Get and put operations
get :: State s s
get = State (\s -> (s, s))

put :: s -> State s ()
put s = State (\_ -> ((), s))

-- Example: A counter using the State monad
counter :: State Int Int
counter = do
    n <- get
    put (n + 1)
    return n

-- Run the stateful computation
-- runState counter 0 => (0, 1)
-- runState counter 1 => (1, 2)

1.8.2 7.2 Category Theory in Type Systems

Category theory provides the foundation for modern type systems:

-- The Curry-Howard correspondence: types as propositions, programs as proofs

-- Product type (A ∧ B)
data Product a b = Product a b

-- Sum type (A ∨ B)
data Sum a b = Left a | Right b

-- Function type (A → B)
type Function a b = a -> b

-- The unit type (⊤, "true")
data Unit = Unit

-- The empty type (⊥, "false")
data Void

-- Logical negation (¬A = A → ⊥)
type Not a = a -> Void

-- Example: Proof of A → (B → A)
implication :: a -> (b -> a)
implication a _ = a

1.9 8. Visualizing Category Theory

We can use various tools to visualize categorical structures:

import matplotlib.pyplot as plt
import networkx as nx

def draw_category(objects, morphisms):
    """
    Draw a category using networkx and matplotlib.
    
    objects: list of object names
    morphisms: list of tuples (source, target, name)
    """
    G = nx.DiGraph()
    
    # Add objects as nodes
    G.add_nodes_from(objects)
    
    # Add morphisms as edges
    for source, target, name in morphisms:
        G.add_edge(source, target, label=name)
    
    # Set layout
    pos = nx.spring_layout(G, seed=42)
    
    # Draw nodes
    nx.draw_networkx_nodes(G, pos, node_size=1000, node_color='lightblue')
    
    # Draw edges
    nx.draw_networkx_edges(G, pos, edgelist=G.edges(), arrowstyle='->', arrowsize=20)
    
    # Draw labels
    nx.draw_networkx_labels(G, pos, font_size=12, font_family='sans-serif')
    
    # Draw edge labels
    edge_labels = nx.get_edge_attributes(G, 'label')
    nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=10)
    
    # Show plot
    plt.axis('off')
    plt.show()

# Example: Draw a simple category with products
objects = ['A', 'B', 'A×B', 'C']
morphisms = [
    ('A×B', 'A', 'π₁'),
    ('A×B', 'B', 'π₂'),
    ('C', 'A', 'f'),
    ('C', 'B', 'g'),
    ('C', 'A×B', '⟨f,g⟩')
]

# draw_category(objects, morphisms)

1.10 9. Conclusion and Further Reading

Category theory provides a powerful framework for thinking about computation and programming. Its abstract nature allows us to discover deep connections between different areas of computer science.

1.10.1 9.1 Key Takeaways

Categories provide a general framework for studying mathematical structures and their relationships
Functors allow us to transform between different categories while preserving structure
Natural transformations capture the relationships between functors
Limits and colimits generalize familiar constructions like products and sums
Adjunctions establish weak equivalences between categories
Monads provide a structured way to handle side effects in functional programming

1.10.2 9.2 Further Reading

“Categories for the Working Mathematician” by Saunders Mac Lane
“Category Theory for Programmers” by Bartosz Milewski
“Abstract and Concrete Categories” by Jiri Adamek, Horst Herrlich, and George Strecker
“Type Theory and Functional Programming” by Simon Thompson
“Homotopy Type Theory: Univalent Foundations of Mathematics” by The Univalent Foundations Program

--- title: "Category Theory" subtitle: "MathPhysCS CodeLab on Category Theory" author: "Rong-Kang Zhang" date: last-modified categories: - Mathematical Logic - Category Theory keywords: - Natural Transformation - Functor - Adjoint Functor - Limits - Programming format: html: toc: true toc-title: "Contents" toc-location: left anchor-sections: true smooth-scroll: true highlight-style: dracula number-sections: true secnumdepth: 3 toc-depth: 5 code-tools: true code-fold: true code-overflow: wrap css: styles.scss # 引用你的 SCSS 文件 bibliography: ../../refs.bib csl: ../../american-mathematical-society.csl eq-prefix: "Eq." fig-prefix: "Fig." tbl-prefix: "Tbl." thm-prefix: "Thm." crossref: fig-title: "Figure" tbl-title: "Table" eq-title: "Equation" thm-title: "Theorem" filters: - E:/apps-in-use/github-desktop/rongkang-zhang/homepage/_extensions/quarto-ext/latex-environment/latex-environment.lua - E:/apps-in-use/github-desktop/rongkang-zhang/homepage/_extensions/pandoc-ext/diagram/diagram.lua - E:/apps-in-use/github-desktop/rongkang-zhang/homepage/_extensions/danmackinlay/tikz/tikz.lua - E:/apps-in-use/github-desktop/rongkang-zhang/homepage/_extensions/quarto-ext/include-code-files/include-code-files.lua environments: framedshaded: framedshaded lrbox: lrbox theorem: theorem lemma: lemma definition: definition proposition: proposition corollary: corollary remark: remark example: example proof: proof tikz: cache: false save-tex: true tex-dir: tikz-tex lightbox: match: auto effect: fade desc-position: right loop: false css-class: "my-css-class" --- # Category Theory: Programming Perspective ## Introduction This document explores category theory from a computational and programming perspective. While category theory is a branch of mathematics, its abstract nature makes it highly relevant to computer science, particularly in the design of programming languages, type systems, and software architectures. In this CodeLab, we will: 1. Implement core categorical concepts in programming languages 2. Explore how category theory influences functional programming 3. Apply categorical patterns to solve computational problems 4. Use visualization tools to understand categorical structures ## 1. Foundational Definitions ### 1.1 Categories :::{.definition #def-category} A **category** $\mathcal{C}$ consists of: 1. A collection of objects $\text{ob}(\mathcal{C})$ 2. For every pair of objects $A, B$, a set $\text{hom}_{\mathcal{C}}(A, B)$ of morphisms (or arrows) from $A$ to $B$ 3. A composition operation $\circ$ that takes morphisms $f: A \to B$ and $g: B \to C$ and produces a morphism $g \circ f: A \to C$ 4. For each object $A$, an identity morphism $\text{id}_A: A \to A$ satisfying: - Associativity: $(h \circ g) \circ f = h \circ (g \circ f)$ - Identity: $f \circ \text{id}_A = f$ and $\text{id}_B \circ f = f$ for all $f: A \to B$ ::: ### 1.2 Programming with Categories Let's implement the concept of a category in Haskell: ```haskell -- Type class for categories class Category cat where -- Identity morphism id :: cat a a -- Composition of morphisms (.) :: cat b c -> cat a b -> cat a c -- Example: The category of Haskell functions instance Category (->) where id x = x (g . f) x = g (f x) ``` In Python, we can represent categories using classes and objects: ```python from abc import ABC, abstractmethod from typing import TypeVar, Generic, Callable A = TypeVar('A') B = TypeVar('B') C = TypeVar('C') class Morphism(ABC, Generic[A, B]): @abstractmethod def __call__(self, x: A) -> B: pass @abstractmethod def compose(self, other: 'Morphism[C, A]') -> 'Morphism[C, B]': pass class FunctionMorphism(Morphism[A, B]): def __init__(self, func: Callable[[A], B]): self.func = func def __call__(self, x: A) -> B: return self.func(x) def compose(self, other: 'FunctionMorphism[C, A]') -> 'FunctionMorphism[C, B]': return FunctionMorphism(lambda x: self.func(other.func(x))) # Identity morphism def identity() -> FunctionMorphism[A, A]: return FunctionMorphism(lambda x: x) ``` ## 2. Functors ### 2.1 Definition of Functors :::{.definition #def-functor} A **functor** $F: \mathcal{C} \to \mathcal{D}$ between categories $\mathcal{C}$ and $\mathcal{D}$ consists of: 1. A mapping from objects of $\mathcal{C}$ to objects of $\mathcal{D}$: $A \mapsto F(A)$ 2. A mapping from morphisms of $\mathcal{C}$ to morphisms of $\mathcal{D}$: $f: A \to B \mapsto F(f): F(A) \to F(B)$ satisfying: - $F(\text{id}_A) = \text{id}_{F(A)}$ for all objects $A$ in $\mathcal{C}$ - $F(g \circ f) = F(g) \circ F(f)$ for all morphisms $f: A \to B$ and $g: B \to C$ in $\mathcal{C}$ ::: ### 2.2 Functors in Programming In Haskell, the `Functor` type class represents endofunctors on the category of Haskell types: ```haskell class Functor f where fmap :: (a -> b) -> f a -> f b -- Laws: -- fmap id = id -- fmap (g . f) = fmap g . fmap f -- Example: Maybe functor data Maybe a = Nothing | Just a instance Functor Maybe where fmap _ Nothing = Nothing fmap f (Just x) = Just (f x) -- Example: List functor instance Functor [] where fmap = map ``` In Python, we can implement functors using generic classes: ```python from typing import TypeVar, Generic, List, Optional, Callable A = TypeVar('A') B = TypeVar('B') class Functor(Generic[A]): @abstractmethod def fmap(self, func: Callable[[A], B]) -> 'Functor[B]': pass class Maybe(Functor[A]): def __init__(self, value: Optional[A]): self.value = value def fmap(self, func: Callable[[A], B]) -> 'Maybe[B]': if self.value is None: return Maybe(None) else: return Maybe(func(self.value)) def __repr__(self): return f"Maybe({self.value})" class List(Functor[A]): def __init__(self, values: List[A]): self.values = values def fmap(self, func: Callable[[A], B]) -> 'List[B]': return List([func(x) for x in self.values]) def __repr__(self): return f"List({self.values})" ``` ## 3. Natural Transformations ### 3.1 Definition of Natural Transformations :::{.definition #def-natural-transformation} A **natural transformation** $\eta: F \Rightarrow G$ between functors $F, G: \mathcal{C} \to \mathcal{D}$ consists of: 1. For each object $A$ in $\mathcal{C}$, a morphism $\eta_A: F(A) \to G(A)$ in $\mathcal{D}$ such that for every morphism $f: A \to B$ in $\mathcal{C}$, the following diagram commutes: $$\begin{CD} F(A) @>{\eta_A}>> G(A) \\ @V{F(f)}VV @VV{G(f)}V \\ F(B) @>{\eta_B}>> G(B) \end{CD}$$ i.e., $G(f) \circ \eta_A = \eta_B \circ F(f)$ ::: ### 3.2 Implementing Natural Transformations In Haskell, natural transformations are represented as polymorphic functions: ```haskell -- A natural transformation from functor f to functor g type NatTrans f g = forall a. f a -> g a -- Example: Natural transformation from Maybe to List maybeToList :: NatTrans Maybe [] maybeToList Nothing = [] maybeToList (Just x) = [x] -- Example: Natural transformation from List to Maybe (taking the first element) headMay :: NatTrans [] Maybe headMay [] = Nothing headMay (x:_) = Just x ``` In Python, we can implement natural transformations using generic functions: ```python from typing import TypeVar, Generic, Callable F = TypeVar('F', bound=Functor) G = TypeVar('G', bound=Functor) A = TypeVar('A') # A natural transformation is a generic function that transforms # an object of functor F to an object of functor G NaturalTransformation = Callable[[F[A]], G[A]] # Example: Natural transformation from Maybe to List def maybe_to_list(maybe: Maybe[A]) -> List[A]: if maybe.value is None: return List([]) else: return List([maybe.value]) # Example: Natural transformation from List to Maybe (taking the first element) def head_may(lst: List[A]) -> Maybe[A]: if not lst.values: return Maybe(None) else: return Maybe(lst.values[0]) ``` ## 4. Limits and Colimits ### 4.1 Product and Coproduct :::{.definition #def-product} The **product** of objects $A$ and $B$ in a category $\mathcal{C}$ is an object $A \times B$ together with projection morphisms $\pi_1: A \times B \to A$ and $\pi_2: A \times B \to B$ such that for any object $C$ and morphisms $f: C \to A$ and $g: C \to B$, there exists a unique morphism $\langle f, g \rangle: C \to A \times B$ making the following diagram commute: $$\begin{CD} C @>{\langle f, g \rangle}>> A \times B \\ @V{f}VV @VV{\pi_1}V \\ A @= A \end{CD} \quad \begin{CD} C @>{\langle f, g \rangle}>> A \times B \\ @V{g}VV @VV{\pi_2}V \\ B @= B \end{CD}$$ ::: :::{.definition #def-coproduct} The **coproduct** of objects $A$ and $B$ in a category $\mathcal{C}$ is an object $A + B$ together with injection morphisms $\iota_1: A \to A + B$ and $\iota_2: B \to A + B$ such that for any object $C$ and morphisms $f: A \to C$ and $g: B \to C$, there exists a unique morphism $[f, g]: A + B \to C$ making the following diagram commute: $$\begin{CD} A @>{\iota_1}>> A + B \\ @V{f}VV @VV{[f, g]}V \\ C @= C \end{CD} \quad \begin{CD} B @>{\iota_2}>> A + B \\ @V{g}VV @VV{[f, g]}V \\ C @= C \end{CD}$$ ::: ### 4.2 Products and Coproducts in Programming In Haskell, products are tuples and coproducts are `Either`: ```haskell -- Product: (a, b) is the product of a and b -- Projections: fst and snd fst :: (a, b) -> a fst (x, _) = x snd :: (a, b) -> b snd (_, y) = y -- Pairing function pair :: (c -> a) -> (c -> b) -> c -> (a, b) pair f g x = (f x, g x) -- Coproduct: Either a b is the coproduct of a and b data Either a b = Left a | Right b -- Injections left :: a -> Either a b left = Left right :: b -> Either a b right = Right -- Case analysis (cotupling) caseEither :: (a -> c) -> (b -> c) -> Either a b -> c caseEither f _ (Left x) = f x caseEither _ g (Right y) = g y ``` In Python, we can implement products as tuples and coproducts as a custom `Either` class: ```python from typing import Tuple, TypeVar, Generic, Callable A = TypeVar('A') B = TypeVar('B') C = TypeVar('C') # Product: tuples are products in Python # Projections def fst(pair: Tuple[A, B]) -> A: return pair[0] def snd(pair: Tuple[A, B]) -> B: return pair[1] # Pairing function def pair(f: Callable[[C], A], g: Callable[[C], B]) -> Callable[[C], Tuple[A, B]]: return lambda x: (f(x), g(x)) # Coproduct: Either type class Either(Generic[A, B]): def __init__(self, is_left: bool, value: A | B): self.is_left = is_left self.value = value @staticmethod def left(value: A) -> 'Either[A, B]': return Either(True, value) @staticmethod def right(value: B) -> 'Either[A, B]': return Either(False, value) # Case analysis (cotupling) def case(self, f: Callable[[A], C], g: Callable[[B], C]) -> C: if self.is_left: return f(self.value) else: return g(self.value) ``` ## 5. Adjoint Functors ### 5.1 Definition of Adjunctions :::{.definition #def-adjunction} An **adjunction** between categories $\mathcal{C}$ and $\mathcal{D}$ consists of a pair of functors $F: \mathcal{D} \to \mathcal{C}$ (left adjoint) and $G: \mathcal{C} \to \mathcal{D}$ (right adjoint) together with a natural isomorphism: $$\mathcal{C}(F(D), C) \cong \mathcal{D}(D, G(C))$$ for all objects $C$ in $\mathcal{C}$ and $D$ in $\mathcal{D}$. ::: ### 5.2 Adjunctions in Programming A classic example of adjunction in programming is the relationship between the `Maybe` type and the `List` type: ```haskell -- The "singleton" functor (left adjoint) data Singleton a = Singleton a instance Functor Singleton where fmap f (Singleton x) = Singleton (f x) -- The "list" functor (right adjoint) -- (List is already a Functor) -- The adjunction between Singleton and List unit :: a -> [a] unit x = [x] counit :: Singleton [a] -> a counit (Singleton [x]) = x counit _ = error "Counit defined only for singleton lists" -- The natural transformations leftAdjunct :: (Singleton a -> b) -> a -> [b] leftAdjunct f x = [f (Singleton x)] rightAdjunct :: (a -> [b]) -> Singleton a -> b rightAdjunct f (Singleton x) = head (f x) -- Partial function! ``` In Python, we can implement this adjunction as follows: ```python from typing import TypeVar, Generic, List, Callable A = TypeVar('A') B = TypeVar('B') # The "singleton" functor (left adjoint) class Singleton(Generic[A]): def __init__(self, value: A): self.value = value def fmap(self, func: Callable[[A], B]) -> 'Singleton[B]': return Singleton(func(self.value)) # The adjunction between Singleton and List def unit(value: A) -> List[A]: return [value] def counit(singleton: Singleton[List[A]]) -> A: # Note: This is a partial function if len(singleton.value) == 1: return singleton.value[0] else: raise ValueError("Counit defined only for singleton lists") # The natural transformations def left_adjunct(f: Callable[[Singleton[A]], B]) -> Callable[[A], List[B]]: return lambda x: [f(Singleton(x))] def right_adjunct(f: Callable[[A], List[B]]) -> Callable[[Singleton[A]], B]: # Note: This is a partial function return lambda singleton: f(singleton.value)[0] ``` ## 6. Monads ### 6.1 Definition of Monads :::{.definition #def-monad} A **monad** on a category $\mathcal{C}$ is a triple $(T, \eta, \mu)$ consisting of: 1. An endofunctor $T: \mathcal{C} \to \mathcal{C}$ 2. A natural transformation $\eta: \text{id}_{\mathcal{C}} \Rightarrow T$ (unit) 3. A natural transformation $\mu: T \circ T \Rightarrow T$ (multiplication) such that the following diagrams commute: 1. Associativity: $$\begin{CD} T(T(T(A))) @>{\mu_{T(A)}}>> T(T(A)) \\ @V{T(\mu_A)}VV @VV{\mu_A}V \\ T(T(A)) @>{\mu_A}>> T(A) \end{CD}$$ 2. Unit laws: $$\begin{CD} T(A) @>{\eta_{T(A)}}>> T(T(A)) \\ @V{id_{T(A)}}VV @VV{\mu_A}V \\ T(A) @= T(A) \end{CD} \quad \begin{CD} T(A) @>{\mu_A}>> T(A) \\ @V{T(\eta_A)}VV @AA{id_{T(A)}}A \\ T(T(A)) @= T(A) \end{CD}$$ ::: ### 6.2 Monads in Programming In Haskell, the `Monad` type class represents monads: ```haskell class Monad m where -- Unit: Inject a value into the monad return :: a -> m a -- Bind: Chain computations (>>=) :: m a -> (a -> m b) -> m b -- Multiplication (derivable) join :: m (m a) -> m a join x = x >>= id -- Laws: -- return a >>= f = f a -- m >>= return = m -- (m >>= f) >>= g = m >>= (\x -> f x >>= g) -- Example: Maybe monad instance Monad Maybe where return x = Just x Nothing >>= _ = Nothing Just x >>= f = f x -- Example: List monad instance Monad [] where return x = [x] xs >>= f = concat (map f xs) ``` In Python, we can implement monads using a generic class: ```python from typing import TypeVar, Generic, Callable, List, Optional A = TypeVar('A') B = TypeVar('B') class Monad(Generic[A]): @abstractmethod def bind(self, func: Callable[[A], 'Monad[B]']) -> 'Monad[B]': pass @staticmethod @abstractmethod def return_(value: A) -> 'Monad[A]': pass def join(self) -> 'Monad[A]': # Default implementation for monads where join is bind with identity return self.bind(lambda x: x) class MaybeMonad(Monad[A]): def __init__(self, value: Optional[A]): self.value = value def bind(self, func: Callable[[A], 'MaybeMonad[B]']) -> 'MaybeMonad[B]': if self.value is None: return MaybeMonad(None) else: return func(self.value) @staticmethod def return_(value: A) -> 'MaybeMonad[A]': return MaybeMonad(value) def __repr__(self): return f"MaybeMonad({self.value})" class ListMonad(Monad[A]): def __init__(self, values: List[A]): self.values = values def bind(self, func: Callable[[A], 'ListMonad[B]']) -> 'ListMonad[B]': result = [] for value in self.values: monad = func(value) result.extend(monad.values) return ListMonad(result) @staticmethod def return_(value: A) -> 'ListMonad[A]': return ListMonad([value]) def __repr__(self): return f"ListMonad({self.values})" ``` ## 7. Applications in Programming ### 7.1 Functional Programming Patterns Category theory has heavily influenced functional programming. Here are some examples: ```haskell -- The State monad for managing stateful computations newtype State s a = State { runState :: s -> (a, s) } instance Functor (State s) where fmap f (State g) = State (\s -> let (a, s') = g s in (f a, s')) instance Monad (State s) where return a = State (\s -> (a, s)) State g >>= f = State (\s -> let (a, s') = g s in runState (f a) s') -- Get and put operations get :: State s s get = State (\s -> (s, s)) put :: s -> State s () put s = State (\_ -> ((), s)) -- Example: A counter using the State monad counter :: State Int Int counter = do n <- get put (n + 1) return n -- Run the stateful computation -- runState counter 0 => (0, 1) -- runState counter 1 => (1, 2) ``` ### 7.2 Category Theory in Type Systems Category theory provides the foundation for modern type systems: ```haskell -- The Curry-Howard correspondence: types as propositions, programs as proofs -- Product type (A ∧ B) data Product a b = Product a b -- Sum type (A ∨ B) data Sum a b = Left a | Right b -- Function type (A → B) type Function a b = a -> b -- The unit type (⊤, "true") data Unit = Unit -- The empty type (⊥, "false") data Void -- Logical negation (¬A = A → ⊥) type Not a = a -> Void -- Example: Proof of A → (B → A) implication :: a -> (b -> a) implication a _ = a ``` ## 8. Visualizing Category Theory We can use various tools to visualize categorical structures: ```python import matplotlib.pyplot as plt import networkx as nx def draw_category(objects, morphisms): """ Draw a category using networkx and matplotlib. objects: list of object names morphisms: list of tuples (source, target, name) """ G = nx.DiGraph() # Add objects as nodes G.add_nodes_from(objects) # Add morphisms as edges for source, target, name in morphisms: G.add_edge(source, target, label=name) # Set layout pos = nx.spring_layout(G, seed=42) # Draw nodes nx.draw_networkx_nodes(G, pos, node_size=1000, node_color='lightblue') # Draw edges nx.draw_networkx_edges(G, pos, edgelist=G.edges(), arrowstyle='->', arrowsize=20) # Draw labels nx.draw_networkx_labels(G, pos, font_size=12, font_family='sans-serif') # Draw edge labels edge_labels = nx.get_edge_attributes(G, 'label') nx.draw_networkx_edge_labels(G, pos, edge_labels=edge_labels, font_size=10) # Show plot plt.axis('off') plt.show() # Example: Draw a simple category with products objects = ['A', 'B', 'A×B', 'C'] morphisms = [ ('A×B', 'A', 'π₁'), ('A×B', 'B', 'π₂'), ('C', 'A', 'f'), ('C', 'B', 'g'), ('C', 'A×B', '⟨f,g⟩') ] # draw_category(objects, morphisms) ``` ## 9. Conclusion and Further Reading Category theory provides a powerful framework for thinking about computation and programming. Its abstract nature allows us to discover deep connections between different areas of computer science. ### 9.1 Key Takeaways 1. Categories provide a general framework for studying mathematical structures and their relationships 2. Functors allow us to transform between different categories while preserving structure 3. Natural transformations capture the relationships between functors 4. Limits and colimits generalize familiar constructions like products and sums 5. Adjunctions establish weak equivalences between categories 6. Monads provide a structured way to handle side effects in functional programming ### 9.2 Further Reading - "Categories for the Working Mathematician" by Saunders Mac Lane - "Category Theory for Programmers" by Bartosz Milewski - "Abstract and Concrete Categories" by Jiri Adamek, Horst Herrlich, and George Strecker - "Type Theory and Functional Programming" by Simon Thompson - "Homotopy Type Theory: Univalent Foundations of Mathematics" by The Univalent Foundations Program