Categories for Everyone!
At Earnest, we like predictable code. Who doesn’t? That can mean different things to different people. Generally, for us, that means having at least some confidence that our code obeys some mathematical laws when possible (this is something you might have picked up on if you read our prior post on our recent adventures in JavaScript data validation).
As such, we have a fair amount of Category Theory floating around parts of the office, that hip new (as recent as 1942!) field of math you might have heard a bit about in relation to functional programming. In this blog post, I thought I’d share some basic examples of categories and a little bit on why we find thinking in terms of them is occasionally handy.
What is a category? To have a category, you first need some stuff, the objects of the category. Then, you need some relationships between those things that behave a certain way (called morphisms). Say you have a relationship between an object A and an object B. Say also you have a relationship between an object B and an object C. Then, you can join those two relationships together to get a new relationship between object A and object C. This is called composition.
Composition of relationships has to obey associativity, which means that it doesn’t matter what order you do the composing in.
Finally, every object has to be related to itself by a unique identity relationship that does precisely nothing.
If you know any Scala, here’s a simplistic typeclass with implementation for the trivial case of functions:
You may have noticed that categories really only support one operation, and that is kind of the whole point of it. Categories only know about composition; it’s literally the only thing you can do. So, thinking in terms of categories forces you to think compositionally. Learning how to think in categories, might help you design in a more compositional style.
Now that we know what we’re talking about a bit, let’s do some examples!
An easy everyday example is that any set can be considered as a category. You’ve got some stuff (the elements of the set) and some relationships (just relate every object to itself). You can draw a picture of it like this:
That’s kind of a boring case, because there are no interrelationships between objects.
What’s an interesting case? Let N be the natural numbers (0, 1, 2, …). It turns out that this may also be seen as a category (in a couple different ways actually). How? It might not be immediately obvious what the composition of two numbers means.
We’re gonna do a trick called Cayley Embedding¹. Associate to every number (say, 5) the function that adds that number to what we’re given (z => z + 5).
In other words, check this here code:
So, we’ve turned elements of N into functions that take elements of N to elements of N, and composing those functions exactly mimics addition! Here’s a picture of what that looks like more or less:
That’s a lot of loops on a single object.
Since evaluating any of our functions (those loops up there) at 0 gives us back the value that would give that very same function, we’ve correctly modeled the natural numbers as a category.
Just to convince you, here’s a direct implementation (no tricky embeddings) in Scala:
Since that got pretty heady, let’s look at a quick computational example. If you know about Promises, then we can talk about a pretty interesting category.
We’re going to think of our objects as the types of possible JavaScript values. For the morphisms, we’re going to think about functions that take a value of some type and return a promise that resolves to a value of some type (maybe the same type, maybe not)².
For example, a morphism in this case might be a function that takes a number, and returns a promise resolving to an array. That function might execute an asynchronous call to a SQL database that takes a user ID and returns a collection of picture IDs, or what have you.
Then, it turns out we have a category. Here’s what the composition and identity look like:
This one is a little too complicated to draw a good diagram.
It might not be obvious, but that composition really is associative, and that promiseIdentity function really is the identity for that composition. This means that pure Promise returning functions form a category in JavaScript, so if you write JavaScript professionally, you might write category theoretic code regularly without thinking too much of it. If this sort of thing interests you, this is called a Kleisli category.
In Scala, you can do the same thing with Futures, Scala’s mechanism for Promise style asynchronous programming (here we’re using Twitter’s slightly more convenient Future). Lo,
Hopefully, that little journey helped you build some intuition about categories and their interest. We took some things that looked like static data being acted upon, and changed them into dynamic elements that compose. In doing that, we changed our perspective from seeing a world made up of objects that are passively manipulated to a world made up of composing processes. Doing this can be a powerful strategy to increase how well and clearly the code you write composes, with all the attendant benefits. Even better, since categories are governed by mathematical laws, everything’s predictable!
Finally, if you’re interested in theory, feel free to contact me on Twitter as Slazasaurus. I’m always happy to share book recommendations and other resources. And if you’re interested in Earnest, we’re hiring!
[1] Or, more generally, the Yoneda Embedding.
[2] The caveat here is that those functions have to be side effect free except for being asynchronous. So, they can’t print to console or anything, they can only possibly be asynchronous. The only thing these functions know about are values and promises of values.
