Category theory

My understanding of this field of mathematics, also known as "the abstraction of all abstractions". Apparently if you try to abstract categories, you just get more categories.

Supposedly category theory is the foundation of many helpful software patterns and how to compose them. I am reading Categories for Programmers to decide for myself whether this is true, and discover whether there are programming super-powers for real life hidden in the abstract land of categories.

Basic stuff:

At its core, a category is a class (collection, more generic than a set) of objects, and a class of morphisms between these objects. The morphisms are closed under composition: if $A, B, C \in o b j (C)$ (the class of objects in category $C$ ), and $f, g \in m o r (C)$ (the class of morphisms between objects in category $C$ ) such that $f : A \to B$ and $g : B \to C$ , then $g \circ f : A \to C$ must also be in $m o r (C)$ . Don't forget, you need identity functions for all objects in the morphisms class too.
However, beyond that, you're free to choose the class of objects and morphisms between them. You can limit your study to numerical functions by choosing the object class to be $Z, Z \times Z$ , then add the necessary functions $i d_{Z}, i d_{Z \times Z}$ , and that in and of itself is a category! But to make it more interesting, you can add $+ : Z \times Z \to Z$ (and then the closure under composition with other operators, of course, which I will not repeat again when we extend a category). But what if we add the curried version of $+$ , meaning we add $(+) : Z \to (Z \to Z)$ , which means we are adding $Z \to Z$ to our objects class (along with a new identity function, which I will not repeat again)?
- I am curious to know: how much do you have to extend (or generalise a category) before you start deducing interesting things? Do findings from categories only really occur at the polymorphic (generic) level?
Categories are not necessarily closed under product or sum, but you can extend a category to include $A \times B$ or $A + B$ for any two objects.
Because of the correspondence between functions on products $f : A \times B \to C$ and their curried equivalents $f_{c} : A \to (B \to C)$ , I will use curried notation here out because it makes it easier to think of collections of functions.
We will often reduce categories in question to their simplest example, like a single object ( $A$ ) category and three (non-identity) functions $f, g, g \circ f : A \to A$ (which as you'll see later, is a categorical monoid).

Examples of categories:

Simple Haskell types (including generics, products and sums, ie $a, a \times b, a | b$ ) and functions between them form a category. I'll bet that even if you add higher-order types (ie Maybe a, List a) it still forms a category, but I'm not sure yet.

Concepts within categories

Two objects $a, b$ are isomorphic if there exist $f : a \to b, g : b \to a$ such that $g \circ f = i d_{a}$ and $f \circ g = i d_{b}$ . We say that $f, g$ form an isomorphism between $a, b$ .
The initial object is the object which has exactly one morphism going to every object in the category. It does not necessarily exist (ie integers as elements with $\leq$ relation as morphisms). If it exists, it is unique up to isomorphism between initial objects. Initial objects are isomorphic to each other (proving this is a fun warm up), and also, their isomorphism is unique (which often ends up being important for constructions).
- The terminal object is the object which has exactly one morphism going from every object in the category. It is the dual of the initial object (ie if a category has an initial object, then when constructing the dual category (aka reversing the arrows), the initial object becomes the terminal object).

Constructing categories from categories

Dual categories. The "dual category" or "opposite category" $C^{o p}$ of a category $C$ has all the arrows reversed; the morphisms of the dual are constructed by swapping the domains and codomains of every morphism in the category. For morphisms defined by composition in $C$ (ie to fulfil closure of morphisms under composition), say $g \circ f$ , this corresponds to constructing $f^{o p} \circ g^{o p}$ in $C^{o p}$ .
- Dual categories are important because for every theorem you prove about a category, you get another theorem for free about its dual. Hence defining concepts like functor and monad also gives us concepts of cofunctor and comonad.
Product of objects. Given two objects $a, b$ , the product is an object $c$ (perhaps written $(a, b)$ or $a \times b$ ) with two projections (morphisms) $f s t : c \to a$ and $s n d : c \to b$ such that for any other $(c^{'}, p^{'} : c^{'} \to a, q^{'} : c^{'} \to b)$ , there is a unique morphism $m : c^{'} \to c$ such that $m$ "factorises" the projections $p, q$ , meaning that $p^{'} = f s t \circ m$ and $q^{'} = s n d \circ m$ . $c$ does not always exist, but when it does, it's unique up to unique isomorphism.
- The "product factoriser" is a function $f a c t o r i s e : (c \to a) \to (c \to b) \to (c \to (a, b))$ such that factorise p q = \x -> (p x, q x).
Coproduct (disjoint sum) of objects. Given objects $a, b$ the coproduct is an object $c$ (perhaps written $a + b$ ) with two injections $l e f t : a \to c$ and $r i g h t : b \to c$ such that for any other $c^{'}, i : a \to c^{'}, j : b \to c^{'}$ , there is a unique morphism $m : c \to c^{'}$ such that $i = m \circ l e f t$ and $j = m \circ r i g h t$ .
- We can define the "coproduct factoriser" as $f a c t o r i s e : (a \to c) \to (b \to c) \to (a + b) \to c$ where factorise i j (Left a) = i a and factorise i j (Right b) = j b

Further concepts with categories

Free categories are constructions of categories from things that conceptually make sense as categories, but need a bit of filling in. For example, making a directed graph into a category by constructing an object class of the nodes, and a morphism class of the edges, but you'll probably need to add to the morphisms until you have all identity functions (edges from nodes to themselves) and transitive edges (if $A \to B, B \to C$ are both in the edges then $A \to C$ must be in the morphisms).
Thin categories have at most one morphism from any object $A$ to any object $B$ ( $B = A$ included). E.g. a preorder, which is a set with relation $\leq$ where for some (but not necessarily all) elements, we have $a \leq b$ , where you may have cycles ( $a \leq b \leq c \leq a$ , but not necessarily $a = b = c$ ).
- A partial order is where $a \leq b \land b \leq a ⟹ a = b$ . That is, you can't have cycles between different elements anymore. Partial orders can be sorted with topological sort (because, of course, you can't sort with a cycle). A partial order with a set is called a "poset".
- A total order is a set $S$ and a relation $\leq$ where every pair of elements is related; that is, for all pairs $(a, b) \in S, a \leq b \lor b \leq a$ .
Monoids make sense as sets and categories.
- Set (aka usual) monoid. A set $S$ with an identity element $0$ and a binary operation $+ : S \to S \to S$ , where $+$ is associative and $s + 0 = s$ for all $s \in S$ .
- Categorical monoid. A category with a single object $S$ and non-identity (example) morphisms $f, g, g \circ f, f \circ g$ . The morphisms need not be all the possible mappings from S to itself, just an arbitrary handful. We can extract a set monoid from a categorical one; the morphisms are the elements of the set, the binary operator is composition, and associativity of the binary operator follows from composition associativity in the category. Likewise, we can construct this category from a set monoid, so we can think of them as the same.