What’s in a Name?
The ABC’s of Category Theory and Functional Programming
Category Theory — Objects and Arrows
Category theory provides a framework for thinking about and discussing general abstract structures in math. It’s three most important concepts are category, functor and natural transformation. Before digging into what these could be, let’s look at category theory from a more general perspective. The difference between category theory and it’s neighbour, set theory, is that while set theory focuses on objects, category theory describes the relationships between objects. In this case objects could be anything, but if it makes it simpler you can think of them as points in a graph. In this case, the edges connecting these dots would together with the dots form a so called category. In category theory, the focus is on those edges, or arrows between objects. They are known as morphisms (or homomorphisms).
The essence of categories lie in the compositions within them. A composition is exactly what it sounds like — you compose one or more things. Below you can see an example. If there are arrows between A and B and between B and C, the arrow from A to C is their composition. This is what the composition of morphisms f and g looks like in math. The name is displayed above the arrow, and the end points display the objects of the morphisms.
Composition is basically gluing arrows together to form bigger arrows. In programming, composition would mean composing functions. For example, you could have a function that multiplies by two and another that multiplies by 3. In whichever way you compose these, if you put number 1 in, you get 6 out. This is also the first rule of composition in category theory: composition is associative, i.e. order doesn’t matter.
The second rule is that for every object A, there exists a unit arrow (identity on A). This might sound far out, but the only thing it means is that the function or arrow returns the object itself, which we are familiar with in programming. In the case of math and natural numbers, this would be the addition of 0. For example, when we add 0 to 1, we get back 1. In category theory, we would call that identity on 1.
Now that we have seen what morphisms (the arrows) and compositions look like, let’s take a closer peek at the concept of category. You can still think of it as the graph with connected dots. The most simple and obvious kind of category is the empty category, or null. It contains no objects. Another type of extremely common category is monoid, which is what comes out of addition or multiplication, like numbers, sets and lists. The only criteria for being a monoid is that it needs to be a set with an associative (any way works) binary operation. For example a boolean can form monoids by operations such as True AND False. In this case, True and False are combined using the binary AND operator, and they form a monoid. String concatenation is another example of creating a monoid. Categories can also be so called free categories, which consist of objects and morphisms but are not monoids.
Now that we know what a category can be and what it might do, let’s move on to functors. A functor is a mapping between categories. Given two categories, it maps all of the objects between them, so that every dot in A has a corresponding dot in B. Not only does it map the objects, but it preserves the connections between them. If in A there is a morphism from a to b, under the functor F in category B the similar morphism exists, now known as Fa to Fb. In programming, the most well known functor is map, which takes an object and, preserving the connections within it, maps it to another category (or collection, list, array etc.). We will take a look at this in practice further down.
The last tricky concept we need to tackle is natural transformation. A natural transformation is a selection of morphisms that connect objects under different functors. For example we might have a category C that contains an object a and two functors (G and F) going from C to D that both produce Ga and Fa, respectively. Doesn’t it seem that both of these objects that came out of a would share some connection? Indeed they do! These functors are connected by a natural transformation.
Making the Computer Go “Beep” with Category Theory
One could say that the history of functional programming begins with the invention of lambda calculus in the 1930’s. Although it’s purpose was to serve as a clarification for the foundations of math, it is now known as the basis of functional programming languages. The idea of functional programming is to approach problems as mathematical functions and avoid changing state or mutating data. In math, a function is nothing but an arrow from a to b, without any logging, giving the dog a cookie or other side effects. Functional programming is declarative rather than imperative, meaning that it uses declaring expressions rather than statements. These were some big words, but here is an example of a very common and simple problem which can be solved in a imperative (using a statement) or declarative (using an expression) way.
Due to having no side effects, functional code is very well suited for working with concurrency. This makes it a relevant paradigm when we need to deal with large amounts of data as fast as possible. It also makes it easier to express what you want to do mathematically, in code.
Pinning Down the Basics
Functional programming is based on the idea of using pure functions. As we found, in math all functions are nothing but mappings between values. A pure function is a function which, given the same input, always returns the same output. Hence, it is independent of state. It should never have side effects. Since a pure function is independent of state, it can be said to have referential transparency, which means it can be replaced by it’s outcome. For example, selectSnack(raining) will always return ‘hot chocolate’, so you can replace it with that string anytime.
Another commonly used term is composition, which refers to the mathematical concept of composition we discussed above. Composition simply means combining functions, most commonly by feeding one into the other. This brings us to another useful way we can think about categories and composability: types. Types imply that some categories cannot be composed. The target must match the source of the arrow. Strongly typed languages force this, whereas loosely typed will probably err in some way when this happens. Only a string can be put into a function that does things to a string.
Fun with Functors
As we stated above, the functor maps the objects of a category to another category, keeping the order in tact. For example in the above code, there are two snacks in the category of snacks. In the new category of drinks, there are the corresponding drinks of each snack.
Moving on to Monads
“Oh, you know some Haskell? I would ask the monad question, if I knew the answer myself!” was a comment I got from a technical interviewer a few months ago. It describes the way this concept is approached in the computer science world: mystified and unanswerable. Now I’ll try to uncover and simplify what it is about, at least to some extent. Monads are more powerful functors, that implement flatMap (whereas functors implement map). The difference between flatMap and map is the side effects happening in flatMap. What makes this concept so hard to grasp is how many things it can do. Simply put, a monad is a thing that glues stuff together. More technically speaking, it forms compositions.
In a pure language such as Haskell, using monads is the only way of doing things that cause side effects, such as logging or passing a token around. For this we need a functor, which outputs a so called Kleisli category, which consists of the functor itself and it’s side effects (m). If for every object is a composition that is associative and has an identity arrow for every object, this functor m is a monad.
Working with Category Theory