Why Are Computer Scientists Talking About Category Theory?

As a student of mathematics, I’m often interested in how fascinating math works its way into other subjects. In particular, I recently became curious about why computer scientists are talking about complicated categorical machinery, and this post is a quasi-answer to this question. As a disclaimer, I’m neither a computer scientist nor a category theorist, so what ensues will be a layman’s (or lay-mathematician’s rather) approach to understanding their connection.

In what ensues, we will not actually need any theory but this post is mostly about developing the requisite language to understand how all of this strangeness came to be. I’m going to routinely defer main definitions to wikipedia, and instead pass to the level of heuristics throughout this post, so that it does not become bloated and technical. Additionally, I’ll assume working knowledge of any first chapter in a category theory textbook (which by happenstance is about as far as the author can speak with any semblance of authority.) I’ll also make the executive  decision to not write in the language of categories (diagrams) or the language of computer science (code) but instead just plain old english and math. In short, by the end of this post, I hope that the reader will feel comfortable reading some of the technical definitions online, which often make this author feel categorically challenged.

Let’s start with the “mathematics” :

A Monoid is an algebraic structure where it “makes sense” to do multiplication. In particular, given a set S, a monoidal structure on S is just a binary operation (\cdot):S \times S \to S that is associative, and has a unit (A group without inverses.) A good first example is (\mathbb N \setminus\{0\},\cdot), but a slightly more relevant example is the collection of functions on some set \{f:S \to S\} with function composition as the binary operation (you give me two functions and I’ll spit out a new one) and the identity functiton as identity (I too regret the last part of that sentence.) More generally, given any object X in a category C, we can consider the collection of endomorphisms X \to X, and these will form a monoid under composition as well.

A Monoidal Category for our purposes is a category that looks like a monoid, afterall since if it walks like a duck and talks like a duck… and in particular, it is a Category C equipped with a bifunctor  C \otimes C \to C (a functor in both arguments) that is associative and has identity “up to natural transformation.” This means basically, that it may not be literally associative since that is probably to stringent a requirement, but there is a way to canonically identify (C \otimes C) \otimes C with C \otimes (C \otimes C). A great first example of this, is the category of sets under cartesian product. For example \mathbb R^2 \times \mathbb R is just \mathbb R^3, and the reason we can write this unambiguously is that \mathbb R \times (\mathbb R \times \mathbb R) is the “same thing.” Maybe a good first pass at gaining intuition here is that we want a category where we can form something kind of like a cartesian product (in fact, this alone gives rise to tons of monoids since any category with finite products provide a monoidal structure); Indeed, the important thing here, is that given two sets A,B, we can regard there product as an element of \mathrm{Set}.

One nice Monoidal Category is the category \mathrm{Ab} of abelian groups, with the bifunctor \otimes. In particular, given two abelian groups we see that \otimes(A,B)=A \otimes B is a bifunctor that is “associative under natural maps and has an identity, namely \mathbb Z. (To see the latter statement, consider the map \mathbb Z \otimes G-\to G given by n \otimes g \mapsto n \cdot g, where multiplication is iterated addition.)

A Monoidal Object is a generalization of monoids that we can form in any monoidal category. It looks like a monoid as well, but we can replace S \times S with C \otimes C as one might expect, and we replace binary “function” with binary “morphism” in our new category. The main obstruction to the last sentence being the end of this conversation is that we don’t have strict associativity and identity, since we don’t have that in general for C \otimes C \otimes C, so there are some diagrams to be drawn here.

If we take our previous monoidal category (\mathrm{Ab},\otimes, \mathbb Z), we can see that if we fix G \in \mathrm{Ab}, we can form a monoidal object by declaring a group homomorphism \cdot:G \otimes G \to G, but in doing so, we use the fact that tensor product is bilinear,  we have the relations g \cdot (a+b)=ga+gb and (a+b)g=ag+bg. In other words, we actually endow G  with a Ring structure. So a monoidal object in this monoidal category is just a ring.

the Category of Endofunctors  is the category of functors \{F:C \to C\} as objects, and natural transformations between them as morphisms. Unsurprisingly, this is a monoidal category. this construction is a specialization (generalization?) of the construction of using endomorphisms of an object in a category to make a monoid under composition.

A Monad is a monoidal object in the category of endofunctors. This has a bit going on, but if we fix a particular endofunctor F, then then we should have a natural transformation \mu:F \circ F \to F that is “associative” and a natural transformation \eta:I \to F, where I is just the identity functor, and we require these to satisfy the so-called coherence conditions.

Here is a near content-less example: we can take functor T(X)  \to \{X\} in \mathrm{Set}. Then, the family of maps \eta_X(X)=\{X\}=T(X). We will Take \muT(T(X)) \to T(X) given by \mu\{\{X\}\}=\{X\}. \mu actually has a slightly different description: take the union of all the sets interior to the outermost brackets, and delete one of the brackets. This is basically, “concatenation” and will play a prominent role in the next example.

Take the endofunctor T:X \to \mathcal{P}(X), the powerset of X. Take \eta:X \to \{X\}. and take \mu as its second description above. This also gives a monadic structure, and introduced a broad class of monads: take a functor F that sends some set X to some object “freely generated” by it, such as all of its subsets, the free group on it, vector space etc. and compose that with the forgetful functor to get back to Set.  “concatenation” of some form, and the underlying set for the inclusion X \to F(X)  will provide monadic structures on \mathrm{Set}.

 

Okay, on to the Computer Science, where I’m going to focus on Haskell. Let’s first just chat about what the monad formalism means here, and then I’ll speak a little bit about why this formalism matters at all.

The first thing to do will to describe the Haskell Category: We consider objects in this categories “types,” so something like floats, lists, tuples, strings etc. and the morphisms between them to be functions between these different types. Note that there are many arrows between different objects, since they are all functions with the appropriate (co)domains.

Now, an endofunctor in \mathrm{Hask} is going to be a functor that sends one type to another, in a way that preserves maps between them. There is a data constructor that takes some type a and maps it to [a], which is a list that contains elements of type a. This data constructor can be made into a functor by specifying what it does to maps  by constructing the function \mathrm{fmap}: (a \to b) \to ([a] \to [b]) defined by applying a morphism a \to b to each element of the list individually.  Indeed, [] defines an endofunctor on \mathrm{Hask}, and we can actually equip this with a monadic structure much like the examples above, by taking \eta:I \to [], by a \mapsto [a] (this is called \mathrm{return} in the language) and we can take the list concatenation operation \mu:[[]] \to [] by [[a]] \mapsto [a] by list concatenation (for example [[1],[2]] \mapsto [1,2]. (This is called \mathrm{Join} in the language.)

This is one example of a monad in Haskell, and there is a sense in which it is the example, if we want to understand how monads are used to “unwrap” data.

Here is an unrealistic first example: suppose we have two morphisms f:a \to [a] and g:a \to [a] (which is not uncommon, perhaps you want to translate a number into a string, which is a list of characters.) Then, we may want a way to compose these morphisms, but there is of course a problem with composing different data types. Ultimately, we want a new function h:a \to [a], but in order to get there, we would want f \circ ([a] \to a) \circ g, so we want some way of taking some [b] and a function g:a \to [a] and combining them (which is the thing in the middle) to form a new function [a] \to [a]. It turns out, this is precisely how we can get a monad to work for us.

First, note that the functor a \mapsto [a] also tells us what to do with functions f:a \to b, namely f \mapsto [f]:[a] \to [a]. Our natural transformation \mu: [[a]] \to [a], allows us to do the following:

    \[\mu \circ([f] \circ g(x)),\]

where g(x) is of type [a], so it gets mapped to type [[a]] by [f], and then unwrapped by \mu to [a], so in other words, given a [a] and some map f:a \to [a], we can use the monadic structure to obtain something of type [a]. This allows us to compose such functions.

From a more practical standpoint, there is the notion of a debuggable function f:a \to \mathrm{maybe}\, a, where \mathrm{mayb}e \,a has two types: \mathrm{just \,}a and \mathrm{nothing}. So, composing said functions allows us to avoid the cumbersome nested if xyz, then return zwy or else break for the composition of functions (more can be found on Haskell wiki.)

Either way, this was just my piece on how in the world category theory weaseled its way into programming (and acually “homomorphisms” of monadic structures give rise to applicative functors which have also found their use in Haskell.)