What’s in a Name?The ABC’s of Category Theory and Functional ProgrammingMagda SteniusBlockedUnblockFollowFollowingJan 29Functional programming is no longer only an academic pastime.
One of the key takeaways from learning functional programming is adjusting ones mind to possibilities and ideas outside of OOP (object-oriented programming).
In this text I’ll try to uncover some of the mathematics and ideas behind those handy functional concepts and take down parts of the brick wall of academic lingo surrounding the theoretical parts of functional programming.
Category Theory — Objects and ArrowsCategory 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 vertices connecting these dots would together with the dots form a so called category.
In category theory, the focus is on those vertices, or arrows between objects.
They are known as morphisms (or homomorphisms).
A (homo)morphismThe 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 “g after f”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.
order doesn’t matter.
Composition is associativeThe 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.
For every object A, there exists a unit arrow “identity on A”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.
AssociativityNow 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.
Morphism a to b under functor FThe 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.
Natural transformation alpha between functors F and GThe best thing about category theory is that one can get these conceptual tools for discussing abstract ideas surrounding functional design.
It simply gives us a wider terminology which we can use to describe the structures we look at (unless we code in Haskell, in which case this vocabulary is part of the language itself).
On the other hand, abstraction itself doesn’t always add value, which Norman Steenrod made a point about in referring to category theory as “general abstract nonsense”.
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.
A statement and an expressionDue 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 BasicsFunctional 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.
Referential transparencyAnother 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.
Function compositionFun with FunctorsAs we already found out, a functor in the mathematical sense is a map between categories.
Despite the fancy sound of it, most developers are already using functors in their daily work.
Using the map functor to create a new arrayAs we stated above, the functor maps the objects of a category to another category, keeping the structure 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 flapMap (whereas functors implement map).
The difference between flatMap and map is the side efWhat 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.
Morphism “a to embellished b” in a Kleisli categoryWhat benefits can we get from knowing what monads are and how they work?.As a first, the concept gives us a framework for rethinking programming with effects.
It also enables us to use effects in pure functional languages like Haskell.
One of the most commonly used monads in Haskell is Maybe.
Another example of a monad is List.
Essentially, it is a kind of type constructor that doesn’t have a pure return type.
In the case of flatMap, the side effect of the mapping is that it flattens the contents by one level.
When map would return a function, flatMap can return the value produced by that function.
Working with Category TheoryThe theoretical parts of functional programming might seem tedious and difficult to grasp due to the so called abstract generic nonsense embedded in it, but in the everyday life of programmers it might turn out to be useful in creating better and more powerful code.
Concepts such as pure functions and functors give us a framework to evaluate out work and the code we write.
I hope this text helped simplifying and demystifying at least some aspects of category theory and functional programming concepts so that the next time anyone reading this ends up in a technical interview, they aren’t afraid of asking or answering “the monad question”.
Resources:Fantasy-land READMEA Monad is just a Monoid in the Category of EndofunctorsFunctors and Monoids (Fun Fun Function)Bartosz Milewski — Programming with MathNCatLab Category Theory.