published Sep 1, 2024

Head::wrap(Head::wrap(Category_Theory)).flatten()

So after reading Math 1001 I found myself going down the rabit hole of Category Theory. Although CT is called “abstract nonsense” by some¹ reading through Bartosz Milewski’s blog² I found it to be quite digestable in the context of programming. However for the life of mine I could not understand why I should actually care about learning CT, so I decided to write down my thoughts here mostly to digest the information for myself.

First of all, Category Theory seems to be the theory of “composable things”. In CT all we care about are objects (dots) and morphisms (arrows). Those morphisms have to be composable, this means that when you can go from A to B and from B to C with an arrow, you must also be able to go to A to C with an arrow.

In an everyday life example this could be a subway map. The dots (objects) are stations and the lines between the stations are the arrows (morphisms). Taking a train is then starting at a given station and following the arrows to your destination. If you take the train from London to Manchester and then from Manchester to Liverpool, it means you are able to go from London to Liverpool with a train, so the arrows are composable.

In programming the dots would be types, and the arrows would be (pure) functions.

type Euro = u64;
type Dollar = u64;

fn add_euro(euro1: Euro, euro2: Euro) -> Euro {
    euro1 + euro2
}

fn add_dollar(dollar1: Dollar, dollar2: Dollar) -> Dollar {
    dollar1 + dollar2
}

fn convert_to_dollar(euro: Euro) -> Dollar {
    // some conversion but we don't care
    dollar
}

fn convert_to_euro(dollar: Dollar) -> Euro {
    // some conversion but we don't care
    euro
}

Now category does not only have objects and morphisms and stops there. With this limited set of things you (mathematicians) can start to define new constructs. Particularly interesting for programmers are functors, monads, and natural transformations.

In short, functors “transform” one category into another while not breaking up the arrows. Monads are functors you can “flatten” (more on that later). Finally Natural Transformations transform one functor into another.

Going back to the example from before, a functor on the subway map could map a very complicated and detailed subway map of the whole country to a simplified map of only the big cities. Many cities would then be condensed to a bigger one and the arrows between the smallers ones would be condensed to one arrow between the big cities. This preserves the direction of arrows and you still can go from one big city to another. (It is now just assumed to can easily get from the big city to the small stations in the city.) By the way, if you keep all the dots and remove some train lines you don’t like this would not be a functor. If you did that now suddenly you can’t go to some places anymore so you broke some arrows. Thus your transformation was not a functor.

In programming functors are quite common. For example a List is usually a functor. It maps every type to a list of that type. If you have a good implementation, you can still use the functions on the List you had on the original types.

type Euro = u64;
type Dollar = u64;

fn add_euro(euro1: Euro, euro2: Euro) -> Euro {...}
fn add_dollar(dollar1: Dollar, dollar2: Dollar) -> Dollar {...}
fn convert_to_dollar(euro: Euro) -> Dollar {...}
fn convert_to_euro(dollar: Dollar) -> Euro {...}

type List<T> = Vec<T>;

dollars: List<Dollar> = vec![1, 2, 3];
inEuros: List<Euro> = dollars.map(convert_to_euro); // << here you are using the original function on the List

What in CT is called a functor is usually called a “convenient container” in programming (because a container where you can’t use the functions you had before is not very convenient).

Now Monads are functors you can “flatten”. In programming this makes a lot of sense. For example if you have a List of Lists in Rust you can flatten it to just a List. It sometimes happens that when you process some type you end up nesting the type in itself, but usually in the end you want to have a flat type again. This also happens with Maybe types if you chain failable operations. A monad is just that, a box that you can flatten.

As far as I understand Natural Transformations are then just maps between functors. So for example mapping a Maybe to List or a List to a Maybe, etc. I guess a well written standard library would contain many of those.

So why should I care about all of this? Reading through many articles I got the sense that understanding CT is not necessary to write good code, but many useful design patterns and constructs in programming map nicely to CT concepts. Also I thought that maybe mapping some CT concepts back to programming might be interesting and useful, but I have not yet found a good example for that. In the mean time there is a great summary of design patterns that are actually CT concepts which I will link here.

Things to read around CT:

Head::wrap(Head::wrap(Category_Theory)).flatten()

Footnotes