---
# System prepended metadata

title: Category Thoery Note
tags: [' class_note_online_course', class_note]

---

# Category Theory for Programmer

[toc]

- Lecture Videos (Youtube): https://www.youtube.com/watch?v=I8LbkfSSR58&list=PLbgaMIhjbmEnaH_LTkxLI7FMa2HsnawM_
- Github repo: https://github.com/leonw774/Category-Theory-for-Programmer
- This note on Hackmd: https://hackmd.io/OkQvCLkHSmaizwJGSJCUUA

# 1. What is category

CATEGORY = (set of objects, set of morphisms)

EMPTY CATEGORY = (Empty set, empty set)

## Objects & Morphisms

In categort theory, objects is any thing in the objects set. Like nodes & arrows in graph, a morphism is a relationship from an object to an other object.

Objects in a category must have an **identity morphism**, an arrow started from itself toward itself.

Morphisms in category must be associative:
  - associative: $f, g, h$ are morphisms, $f \circ (g \circ h) = (f \circ g) \circ h$

## Some special morphisms

A morphism $f: x → y$ is **monomorphisms**
- if $f \circ g1 = f \circ g2$ implies $g1 = g2$ for all morphisms $g1, g2: z → x$.
- Monomorphisms has a **left inverse** if there is a morphism $g: y → x$ such that $g \circ f = id_x$.

A morphism $f: x → y$ is **epimorphism**
- if $g1 \circ f = g2 \circ f$ implies $g1 = g2$ for all morphisms $g1, g2: y → z$.
- Epimorphism has a **right inverse** if there is a morphism $g: y → x$ such that $f \circ g = id_y$.

A morphism $f: x → y$ is **isomorphism**
- if there exists a morphism $g: y → x$ such that $f \circ g = id_y$ and $g \circ f = id_x$.
- $g$ is called simply the **inverse** of $f$.

## Pure vs. Dirty Function

In programming, a pure function is a function that is stable from its input types to output types, it can not be effected by anything out of its scope and have no side effect outside its scope.


# 2. Some Categories

## Free Categories

A category is free category iff $∀$ morphisms $f, g$ , $(f \circ g)$ is also in its morphisms. Example: `funciton-composition.cpp`

## Monoid

Monoid is a kind of group that is simplest category
Monoid $(S, \cdot)$ has:

- A binary operation \dot
    + closed
    + associative
- The identity

The group $(Z^+_N, +)$ is a monoid where $Z^+_N$ is set of positive finite integers smaller than $N$, $N$ is a prime number, and $+$ is a binary operation of addition modulo N.

To see monoid as category:
- The singleton object $S$
- The morphisms are $a$, where $a \in S$
- The composition of morphisms: $a \cdot b$
- The identity morphism is the identity element


# 3. Kleisli Categories

Consider following function:

``` C++
std::string logger;
bool neg(bool b) {
    logger += "Neg!";
    return !b;
}
```

This function is not a pure function as it is not stable AND have side effect. To rewrite it as a pure function, we let the output type of function be an *embellished type* made of `bool b` and `string logger`:

``` C++
typedef pair<bool, string> bool_writer;
bool_writer neg(bool n) {
    return bool_writer(!n.first, "Neg!");
}
```

## Definition

We want to define a function composition operater that *chain up* our log strings together. There is a category out of it: Kleisli category:

- Let $m$ be a morphism that make the input/output of a function into *embellished type*.  
- $m$ is a part of so-called *monad*. (Detailed in latter chapter.)  
- Let f, g be morphisms in Kleisli Category:  
  - $f: t_1 → m(t_2)$
  - $g: t_2 → m(t_3)$
- The composition under Kleisli is $(g \circ f): t_1 → m(t_3)$

## Comparison table

Let's say there is a category $C$, object $x, y, z$ and two morphisms $f: x → y$ and $g: y → z$.

Their Kleisli counterpart over morphism $m$ are category $C_k$, object $x', y', z'$ and two morphisms $f': x' → y'$ and $g': y' → z'$.

| $C$        | $C_k$       |
| ---        | ---        |
| $m$        | $id_{X'}$  |
| $m \circ f$    | $f'$       |
| $m \circ g$    | $g'$       |
| $m \circ g \circ f$| $g' \circ f'$  |

### Example Code

`kleisli.cpp`


# 4. Initial, Terminal Object & Duality

## Initial and Terminal Object

- An object $i$ is a inital object in $C$ if for every object $x$ in $ob(C)$, there exists exactly one morphism $i → x$.
- An object $t$ is a terminal object in $C$ if for every object $x$ in $ob(C)$, there exists exactly one morphism $x → t$.  

Initial & terminal objects are *unique up to unique isomorphism*.

### Example

- The empty set is the unique initial object in *the category of sets*. Because there is exactly one empty function for each set, thus the empty function $\varnothing → x$ is not equal to $\varnothing → y$ if and only if $x \ne y$
- Every one-element set (singleton) is a *terminal object* in *the category of sets*.

## Opposite Category

$C_{op}$ of a given category $C$ is formed by reversing the morphisms, i.e. interchanging the source and target of each morphism.

## Duality

Given a statement regarding the category $C$, by interchanging the source and target of each morphism as well as interchanging the order of composing two morphisms, a corresponding dual statement is obtained regarding the opposite category $C_{op}$. In other words, if a statement is true about $C$, then its dual statement is true about $C_{op}$.

Applying duality, this means an *initial object* in a category $C$ is a *terminal object* the category $C_{op}$


# 5. Product & Coproudct

## Definition

A **product** of object $a$ and $b$ is a object $c$ equipped with two morphisms $p_1: c → a$ and $p_2: c → b$ satisfying the following universal property:
- For every object $d$ equipped with any pair of morphisms $q_1: d → a$ and $q_2: d → b$ there is a *unique* morphism $m: d → c$ such that $q_1 = p_1 \circ m$ and $q_2 = p_2 \circ m$. (We say that $m$ factorize $q_1$ and $q_2$)

```
 D (any product candidate)
    |        |         |
(q1)| (exist unique m) |(q2)
    v        v         v 
    A  <-p1- C -p2->   B 
```

```mermaid
graph TD
    D -->|q1| A
    C -->|p1| A
    C -->|p2| B
    D -->|q2| B
    D -.->|!m| C
```

We denote the product of $a$ and $b$ as $a \times b$

Whether a product exists may depend on the category or on $a$ and $b$. If it does exist, *it is unique up to canonical isomorphism*, so one may speak of *the* product.  
The product is the terminal object in the category of product candidates.

The morphisms $p_1$ and $p_2$ are called the **canonical projections** or **projection morphisms**.

## Examples of Product

The classic example of product is a **pair**. But to make a clearer example, let's say we want a class for the product of `int` and `bool`. This class `Product` will have two method:

``` C++
class Product {
    int toInt(); // Product -> int
    bool toBool(); // Product -> bool
}
```

How do we know whether a implementation of `Product` is the product of not? 

``` C++
class BadProduct {
    int data;
    int toInt() { return data; }
    bool toBool() { return true; }
}

class CounterBadProduct {
    int data1
    bool data2;
    int toInt() { return data1; }
    bool toBool() { return data2; }
    BadProduct toBadProduct(); // does not exist
}
```

Here, `BadProduct` is not a product of `int` and `bool`, because there is a `CounterBadProduct`. We expect for every instance `p` of `CounterBadProduct`, it holds that `p.toBool() == p.toBadProduct().toBool()`. But apparently it is not the case if `p.toBool() == false`.

``` C++
class BadProduct2 {
    int data1;
    int data2;
    bool data3;
    BadProduct2(int d1, int d2, bool d3) :
        data1(d1), data2(d2), data3(d3) {};
    int toInt() { return data1; }
    bool toBool() { return data3; }
}

class CounterBadProduct2 {
    int data1;
    bool data2;
    int toInt() { return data1; }
    bool toBool() { return data2; }
    BadProduct2 toBadProduct2() { // is not unique
        return BadProduct2(data1, /* can be any integer */, data2);
    }; 
}
```

In this case, there is `toBadProduct2()` such that, for every instance `p` of `CounterBadProduct2`, it holds that `p.toBool() == p.toBadProduct2().toBool()` and `p.toInt() == p.toBadProduct2().toInt()`. However, `toBadProduct2()` is not unique. So `BadProduct2` is not the product of `int` and `bool`.

``` C++
class PossibleProduct {
    int data1;
    int toInt() { return data1 / 2; }
    bool toBool() { return data % 2 > 0; }
}

class CounterPossibleProduct {
    int data1;
    bool data2;
    int toInt() { return data1; }
    bool toBool() { return data2; }
    BadProduct CounterPossibleProduct(); // could exist if int is a infinite set
}
```

If cardinality of `int` is infinite, then this `PossibleProduct` is a product of `int` and `bool`. However, in C++, cardinality of `int` is finite. So it can't be the product in this programming language, considering an instance `p` of `CounterPossibleProduct` where `p.toInt() == pow(2, 62)`.

## What is "unique up to isomorphism"

Unique up to isomorphism means that all the objects satisfying a given definition are isomorphic -- there must exist an isomorphism between those objects.  

if every isomorphism between those objects are unique, it is called **"unique up to *unique* isomorphism"**

### Why are they "unique"?

All isomorphic objects have the same relationship with other objects.   

Suppose $a \simeq b$ with isomorphism $α: a → b$, then for all object $y$, there are $Hom(a, y)$ and $Hom(b, y)$ and a bijection function $ϕ: Hom(a, y) → Hom(b, y)$.  

$Hom(a, y)$ means the set of all morphism from $A$ to $Y$

Because for all $f: a → y$ and $g: b → y$:
$$
\begin{aligned}
    ϕ(f) &= g = f \circ α^{-1} \\
    ϕ^{-1}(g) &= f = g \circ α \\
\end{aligned}
$$

we show that $ϕ^{-1} \circ ϕ: Hom(a, y) → Hom(a, y)$ is the identity function:

$$
\begin{aligned}
    (ϕ^{-1} \circ ϕ)(f) &= ϕ^{-1}(ϕ(f)) \\
    &= ϕ^{-1}(f \circ α^{-1}) \\
    &= f \circ α^{-1} \circ α \\
    &= f \circ id_a \\
    &= f \\
\end{aligned}
$$

Strictly speaking we should also show that $ϕ \circ ϕ^{−1}$ is also the identity function, but the proof is almost identical so we’ll omit it.

So we have shown that **there is a bijection between sets of morphisms of isomorphic objects**, and therefore they are formally of the same shape.

## Coproduct: Dual of Product 

Coproduct is basically the product with reverse direction of morphisms in the definition.

Let object $C$ be the product of object $A$ and $B$, the coproduct of $C$ is $C_{op}$ equipped with two morphisms $p_1: a → c$ and $p_2: b → c$ satisfying the following universal property:  
 - For every object $d$ and every pair of morphisms $q_1: a → d$ and $q_2: b → d$ there is a *unique* morphism $m: c → d$ such that $q_1 = (m \circ p_1)$ and $q_2 = (m \circ p_2)$. (We say that $m$ factorize $q_1$ and $q_2$)

We denote the product of $A$ and $B$ as $A \oplus B$

The programming counterpart of a coproduct is a **tagged-union**. Consider a structure `Either` that can be either a type A or type B but not both. We can implement it in this way:


``` C++
// The object Either is the coproduct of type A and type B
template <typename A, typename B>
class Either {
    private:
    enum {isLeft, isRight} tag;
    A left;
    B right;

    public:
    // mapping from A -> Either
    Either set(A a) {
        this.tag = isLeft;
        left = a;
    }

    // mapping from B -> Either
    Either set(B a) {
        this.tag = isRight;
        right = b;
    }

    // return defaultValue if Either is not type A currently
    A getLeft(A defaultVal) {
        return (this.tag == isLeft) ? this.left : defaultVal;
    }

    // return defaultValue if Either is not type B currently
    B getRight(B defaultVal) {
        return (this.tag == isRight) ? this.right : defaultVal;
    }
}
```

## Product and Coproduct as Algebra

A category and product/coproduct forms symmetric monoid.

Commutativity: it is pretty obvious that there existed a unique isomorphism from $a \times b$ to $b \times a$, which is $Swap()$.

Associativity: we can find an isomorphism from $a \times (b \times c)$ to $(a \times b) \times c$. To show that, consider the functions that turns $(a, (b, c))$ into $((a, b), c)$. Those functions exists and all have inverses.

Identity:
- For product, it is the terminal object $t$.
- For coproduct, it is the initial object $i$.

Let $b = a \times t$, $p: b → a$, and $u_b: b → t$. Because the uniqueness of ternimal morphisms $u_b$ is unique.

Considering $a$ itself as the product candidate with $id_a: a → a$ and $u_a: a → t$. We then have an unique morphism $m: a → b$. By the universal property of the product, $id_a = p \circ m$ and $u_a = u_b \circ m$.

Consider:

$$
\begin{aligned}
    u_a &= u_b \circ m \\
    u_a \circ p &= u_b \circ m \circ p \\
\end{aligned}
$$

since $u_a \circ p$ is morphism from $b → t$, it is unique, therefore $u_a \circ p = u_b$. We have:

$$
u_b = u_b \circ m \circ p \\
$$

By uniqueness of identity, $m \circ p = id_b$

Since $p \circ m = id_a$ and $m \circ p = id_b$. $p$ is an isomorphism. Thus $b \simeq a$.

In similar way, we can prove the identityness of initial object $I$ in coproduct operation.

Product is **distributive** with respect to coproduct. It makes the category equipped with product and coproduct a **semi-ring**.

In C++17 `std::optional<T>` is the coproduct of a initial object `nullopt_t` and the type `T`. We can write it in algebra as $optional(T) = 1 \oplus T$

In Haskell, the `List` type is recursively defined as:

```Haskell
data List x = Empty | x : (List x)
```

We can write down the difinition in algebra:

$$
\begin{aligned}
List(x) &= 1 + x \times List(x) \\
List(x) &= 1 + x \times (1 + x \times List(x)) \\
List(x) &= 1 + x \times 1 + x \times x \times List(x) \\
\vdots \\
List(x) &= 1 + x + x^2 + x^3 \cdots
\end{aligned}
$$

# 6. Functors

**Functor** is the mapping from category to category.

To map two categorys $C$ and $D$:
- Map the set of objects in $C$ to the set of objects in $D$
- Map the set of morphisms from $C$ to the set of morphisms in $D$, in the way that **structure is preserved**

For a functor $F: C → D$, for all $f: x → y$ and $g: y → z$ in $C$, it holds that:
1. $F(f): F(x) → F(y)$
2. $F(g \circ f): F(x) → F(z) = F(g) \circ F(f)$
3. $F(id_x) = id_{F(x)}$

```mermaid
flowchart TB
  subgraph domainCategory
    x -- f --> y
    y -- g --> z
    x -- "g∘f" --> z
  end
  subgraph targetCategory
    Fx["F(x)"] -- "F(f)" --> Fy["F(y)"]
    Fy -- "F(g)" --> Fz["F(z)"]
    Fx -- "F(g∘f)" --> Fz
  end
  x -.-> Fx
  y -.-> Fy
  z -.-> Fz
```

**Functors are morphisms.** They can do compositions too. For categories $C, D, E$, if there are functor $F: C → D$ and $G: D → E$, we can have composed functor $H = G \circ F: C → E$.

Functors and categories make a **category of categories**.

## Special Functors


- **Faithful functor** is injective on the morphism sets
- **Full functor** is surjective on the morphism sets.
- **Constant functor** at $x$, denoted as $\Delta_X: C → D$, maps all objects from category $C$ to a fixed object $x \in D$ and maps all the morphisms to the identity morphism $id_x$.
- **Endofunctor** maps a category to itself.
- **Identity functor** maps category to itself and nothing is changed.
- **Contravariant functor** $F: C → D$ satisfies $F(g \circ f) = F(f) \circ F(g)$, in other words it, the second condition is reversed. We can write a contravariant functor in normal/covariant functor as $F: C_{op} → D$
- **Presheaf** on a category $C$ is a functor $F: C_{op} → \mathbf{Set}$

## Examples of functor in programming

### Function Mapper

Let say we have some functions that input and output numbers (`int`, `float`, `double`, etc.). But at certain point, we want these functions to work on numbers encoded as `string`. In this case, a functor to wrap the functions is useful. See example code: `functor.cpp`

### Safe `list::pop_front`

A standard C++ `list::pop_front` function has undefined behavior when the input list is empty. It is good that we return a `optional<list<T>>` object for safety. However, we don't want to re-write the functions working on `list` for `optional<list>`. We can simply write the functor `optionalized()` to transform the original function from category of `T` to the category of `optional<T>`.

``` C++
template <typename T>
std::optional<std::list<T>> safe_get_tail(std::list<T> list) {
    if (list.size() == 0)
        return std::nullopt;
    std::list<T> resultList(list);
    resultList.pop_front();
    return resultList;
}

template <typename T, typename U>
auto optionalized(T (*func)(U)) {
    return [func] (std::optional<U> input) {
        if (input)
            return func(input);
        return std::nullopt;
    }
}

double square_map(list<double> list) {
    std::list<double> resultList;
    std::transform(list.begin(),list.end(),resultList.begin(),
        [](double x) {return x * x;}
    );
    return resultList;
}

int main() {
    std::list<double> goodList = {1, 3, 5, 7, 9};
    std::list<double> emptyList = {};
    auto goodTail = safe_get_tail(goodList);
    auto emptyTail = safe_get_tail(emptyList);
    auto goodSquaredTail optionalized(square_map)(goodListTail);
    auto emptySquardTail optionalized(square_map)(emptyTail);
    return 0;
}
```

# 7.1 Bifunctors

A **bifunctor** is a functor
- from a **product category**
- to a category

### Product Category

Let there be two category $C, D$, the product of $C$ and $D$ contains all possible the pairs of objects and morphisms between $C$ and $D$, that is
- $ob(C \times D) = \{ (x, y) \mid x \in ob(C), y \in ob(D) \}$
- $mor(C \times D) = \{ (f, g) \mid f \in mor(C), g \in mor(D) \}$

The morphism composition works like vectors.

So a bifunctor takes the form of $F: C \times D → E$.

### Difinition

A bifunctor $F: C \times D → E$, for all morphism $(f_1, f_2): (x_1 → y_1, x_2 → y_2)$ and $(g_1, g_2): (y_1 → z_1, y_2 → z_2)$, it holds that
- $F(f_1, f_2): F(x_1, x_2) → F(y_1, y_2)$
- $F((g_1, g_2) \circ (f_1, f_2)): F(x_1, x_2) → F(z_1, z_2) = F(g_1, g_2) \circ F(f_1, f_2)$
- $F(id_{x_1}, id_{x_2}) = id_{F(x_1, x_2)}$


### Pair of Objects and Morphisms

The product or coproduct of every pair of object do not necessary exists. But if they do, we can construct a new category $C'$ that
- $ob(C') = \{ x \times y \mid x \in ob(C), y \in ob(D) \}$
- $mor(C') = \{ f \times g \mid x \in mor(C), y \in mor(D) \}$

Same with coproduct:
- $ob(C'_{op}) = \{ x \oplus y \mid x \in ob(C), y \in ob(D) \}$
- $mor(C'_{op}) = \{ f \oplus g \mid x \in mor(C), y \in mor(D) \}$

And there are obvious bifunctors $F': (C \times D) → C'$ and $F'_{op}: (C \times D) → C'_{op}$

### Wait... What is the Product and Coproduct of Morphism?

The product of morphisms $f: a → a'$ and $g: b → b'$, denoted by $f \times g$, is the unique morphism that

$$
f \times g: (a \times b) → (a' \times b')
$$

$f \times f'$ is unique because
- As the definition of product of objects says, object $(a \times b)$ has morphism $p: (a \times b) → A$ and $q: (a \times b) → b$
- We have composite morphisms $f \circ p: (a \times b) → a'$ and $g \circ q: (a \times b) → b'$
- The definition of product of objects also says that, for any object that has morphism to $a'$ and $b'$, there exists an unique morphism from that object to $a' \times b'$
- So, $(a \times b) → (a' \times b')$ is unique.

Similar proof goes with coproduct.

### Examples of Bifunctor in Programming

In Haskell, bifunctor looks like

``` haskell
class Bifunctor f where
    bimap (a -> a') -> (b -> b') -> (f a b -> f a' b')
```

The `Either` class, defined earlier in C++ to explain coproduct, is a bifunctor if it can be applied on functions

``` C++
// The object Either is the coproduct of type A and type B
template <typename A, typename B>
class Either {

    /* ... */

    // map two functions into one
    template <typename P, typename Q>
    auto either_do(
        P (*funcL)(A),
        Q (*funcR)(B)
    ) {
        return [funcL, funcR] (Either<A, B> input, A lDefault, B rDefault) {
            Either<P, Q> result;
            if (input.tag == isLeft)
                result.set(
                    funcL(input.getLeft(lDefault))
                );
            else
                result.set(
                    funcR(input.getRight(rDefault))
                );
            return result;
        }
    }
}
```

This bifunctor `Either`, maps function pair `P funcL(A)` and `Q funcR(B)` into `Either<P, Q> ()(Either<A, B>)`.

# 7.2 Monoidal Categories

A monoidal category $(C, \otimes, I)$ is consisting of
- A category $C$.
- A bifunctor $\otimes: C \times C → C$. (binary operation)
  - The $\otimes$ is called **tensor product**
  - $\otimes$ is *associative (up to natural isomorphism)*
- An unit object $e \in ob(C)$ such that $\forall a \in ob(C), (\otimes(e, a) \simeq a \land \otimes(a, e) \simeq a)$. (identity element)
- Three natural isomorphisms are involved
  - The associator
    - $α_{a,b,c}: \otimes(\otimes(a, b), c) → \otimes(a, \otimes(b, c))$
  - The left and right unitor
    - $λ_a: \otimes(e, a) → a$
    - $ρ_a: \otimes(a, e) → a$

We will write $\otimes(a, b)$ as $a \otimes b$ from now on.

## Example of monoidal categories

Let make a simple monoidal category from the category of C++ `string`. It has a simple bifunctor `concat`. The application of `concat` is to concatenate two strings. The unit object in this monoidal category should be a instance of string `e`, such that `Concat(e, x) == Concat(x, e)`. This instance of string is obviously an empty string. The implementation is in file `monoidalCategory.cpp`.

Note that, in the monoidal category of string concatenation, the morphism between strings are *permutations*.

# 7.3 Profunctor

