Category Theory You're Already Using
Tags: categorytheory, haskell, javascript
Published: 2020-02-27 23:56:40

---
title: Category Theory You're Already Using
published: true
description: 
tags: Category Theory, Haskell, JavaScript
---

[Category Theory](https://en.wikipedia.org/wiki/Category_theory) has a reputation for being abstract, thorny, complicated, difficult, high-level, and for nerds. While this characterization is not wholly without merit, the truth is closer to that of many other "advanced" CS topics: the pool gets very deep indeed, but even the shallow end has its charms. In the same way that you don't have to fully grok the depths of the V8 engine to write JavaScript, you don't have to understand, e.g. [Kan extensions](https://en.wikipedia.org/wiki/Kan_extension) to use category theory.


Let's take a tour of some categories that, as the title of this post suggests, you're already using in your everyday programming. We'll start basic, and work our way towards the legendary [burrito](https://byorgey.wordpress.com/2009/01/12/abstraction-intuition-and-the-monad-tutorial-fallacy/) itself, the dreaded _monad_. I'll describe the categories in terms of Haskell typeclasses, which are analogous to interfaces in languages like Go or Typescript, and also give some non-Haskell examples, because, again: _you are already using this stuff_!


### Semigroup
A _semigroup_, in the most basic terms, is something you can stick together. In slightly more complex terms:

```haskell
class Semigroup a where
    (<>) :: a -> a -> a
```
This looks a bit scary, but all it means that if some type is a `semigroup`, there's a function called `<>` that combines two instances of that type together. It's also specified that `<>` is _associative_, i.e. `b <> (c <> d)` returns the same thing as `(b <> c) <> d`.

You can probably think of some types you use everyday that meet this criterion, but put a pin in it because the ones you're thinking of are probably actually instances of...


### Monoid
A _monoid_ is a _semigroup_ plus an _identity element_. In Haskell terms:

```haskell
class Semigroup a => Monoid a where
    mempty :: a
```
`mempty` is short for `monoid empty` (because naming things is hard) and is the "identity element" for the monoid in question, such that `mempty <> b` and `b <> mempty` are the same as just plain `b`.

I didn't come up with any examples of _semigroups_ just now, because most things that look like _semigroups_ are actually _monoids_, due to the presence of the identity element:

```python
[1,2,3] + [4,5 6] == [1,2,3,4,5,6]
[1,2,3] + [] == [1,2,3]
[] + [1,2,3] == [1,2,3]

"abc" + "def" == "abcdef"
"abc" + "" == "abc"
"" + "abc" == "abc"

1 + (2 + 3) == (1 + 2) + 3
0 + 1 == 1
1 + 0 == 1

2 * (3 * 1) == (2 * 3) * 1
1 * 2 == 2
2 * 1 == 2
```
The last 2 examples highlight a crucial fact about monoids, and categories in general--one cannot simply say that some type "is a monoid" or not. Rather, "being a monoid" involves not just a type, but an identity element _and_ the `<>` function. Thus, positive integers "are a monoid" with `mempty` as `0` and `<>` as `+`, but _also_ "are a monoid" with `mempty` as `1` and `<>` as `*`. Obviously, `x * 0 != x` and `x + 1 != x`; you need all the pieces.



### Functor
A _functor_ is, basically, kind of, at first approximation, a container. In different terms, a _functor_ is something whose "contents" can be "mapped over," i.e. changed, possibly to a different type. In Haskell terms:

```haskell
class Functor f where
    fmap :: (a -> b) -> f a -> f b
```
This also seems scary, but isn't, really. `f a` is a _functor_ "containing" stuff of type `a`, and `(a -> b)` is Haskellese for "a function from type `a` to type `b`," so all `fmap` does is apply a function to every element in a _functor_. A lot of other languages drop the "f" and just call it `map`:


```javascript
[1,2,3].map(x => x + 1) == [2,3,4]
```

```python
l = [1,2,3]

def f(x):
    return x + 1

list(map(f, l)) == [2,3,4]

# or

[f(v) for v in l] == [2,3,4]
```

(N.B: in Python 3.x, `map` produces an _iterator_, which we have to then turn into a list. The reasons for this are beyond the scope of this post, but are worth it, believe me.)


_**DIGRESSIONS INCOMING, FEEL FREE TO SKIP**_
##### Digression 1
The definition above is limited to just one `a`, but we can define _functor_ instances for types that "contain" more than one type! In Haskell, lists can only contain one type, but tuples can contain multiple types (and, in fact, are basically defined as all the types they contain):

```haskell
one :: (Int, String) = (1, "one")
two :: (Int, String, List Int) = (2, "two", [1, 2])

```
Similarly, (hash) maps are defined by the types of their keys and values:
```haskell
strIntMap :: Map String Int = fromList [("one", 1), ("two", 2)]
intListMap :: Map Int [Int] = fromList [(1, [1,2]), (2, [2,3,4])]
```
(ignore the `fromList` thing, that's just how Haskell displays hashmaps.)

We define _functor_ instances for types like this by treating the right-most type as our `a`, and the rest of it as our `f`:

```haskell
instance Functor (b,) where
    fmap func (x, y) = (x, func y)
instance Functor (Map k) where
    fmap func m = <definition omitted because it's scary and irrelevant>
```
This seems like a lot but the upside is that you can use `fmap` on _anything_ that's a `functor` instance! You don't have to worry about `.map` vs `.forEach` vs `.dictMap` vs `.treeMap` vs whatever.
##### Digression 2
The reason I was so hedgy about equating functors and containers earlier is that there are things that _are_ functors but _aren't_ containers, really, like...functions! Yes, functions are functors! As I mentioned before, Haskell represents functions as `a -> b`. We can treat this like we treated other multi-type functors, like hashmaps and tuples--`(a ->)` becomes our `f`, and `b` becomes our `a`:

```haskell
instance Functor (a ->) where
    fmap f2 f1 = \x -> f2 (f1 x)
```
`\x -> ...` is how Haskell represents anonymous/lambda functions, so this takes two functions and returns another function! If this blows your mind, we can retreat briefly to the container analogy. Take a function like `\x -> show x` (or `lambda x: str(x)`, or `x => String(x)`). We _could_ implement this function, basically, as a hashmap:


```haskell
addOneFunc :: Int -> String = \x -> show x
addOneMap :: Map Int String = fromList [(0, "0"), (1, "1"), (2, "2"), (3, "3")...]
```
Obviously, we _would never do this_, because it's incredibly inefficient and basically impossible in most programming languages. But we _could_, and then we'd see that we could use the same `functor` instance we had before, where `Map Int` is our `f`, and `String`, on the right, is our `a`. Ta-da!
_**END OF DIGRESSIONS, YOU CAN START READING AGAIN**_

### Applicative
Full disclosure: _applicative_ is important in Haskell, but, like _semigroup_, I can't really think of how to show its use in other languages. Briefly, it's kind of a "next-level" _functor_, where the function(s) are _also_ in a "container":

```haskell
instance Functor f => Applicative f where
    pure :: a -> f a
    <*> :: f (a -> b) -> f a -> f b
```
Cool, great. Get a glass of water, and pat yourself on the back for sticking with me this long, because now we're going to move on to the fear of FP neophytes everywhere, the slayer of analogies, the big beast:


### Monad
We're In It Now, so let's just dive in and start with the typeclass, as usually presented:

```haskell
instance Monad f where
   return :: a -> f a
   >>= :: f a -> (a -> f b) -> f b
```

If `return` looks like `pure`, well, that's because it actually is. _applicative_ was discovered and popularized after _monad_ made it into standard Haskell, so for a while `pure` and `return` were separate. This has since been rectified, such that current Haskell has

```haskell
instance Applicative f => Monad f where
    return = pure
    >>= :: f a -> (a -> f b) -> f b
```

Monads get a lot of pixels dedicated to them. If you get nothing else from this post, I want it to be this: monads aren't scary. Take a closer look at `>>=`:

```haskell
>>= :: f a -> (a -> f b) -> f b
```

For kicks, let's specialize it...

```haskell
>>= :: [a] -> (a -> [b]) -> [b]
```

Does it possibly [remind you of anything](https://developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects/Array/flatMap)?

Yes: it's just `flatMap`. That's it, that's the whole typeclass. 

I'm not even joking. Yes, it turns out that you can also use monads to do IO in a type-safe and "pure" way, but that's just a bonus. It's really just `flatMap`, but generalizable over a whole bunch of things besides lists, in the same way that _functor_ is. Every time you use `flatMap`, every time you write a nested `for` loop, you're using a monad. Category theory is on your side, whether you know it or not!

---
#### Postscript and further reading
Like I said, there are a _lot_ of "monad tutorials" out there. My recommendation is: skip 'em. You know what monads are now, go out and be smug about it with my blessings.

If you do want to read more, written by people who are smarter and more eloquent than I am, I recommend the following:

[Category Theory For Programmers](https://github.com/hmemcpy/milewski-ctfp-pdf) -- An absolutely fantastic intro to Category Theory. I've read the first 2/3rds or so a half-dozen times--I've never actually finished it because it goes _way_ far, beyond monads and into adjunctions, kan extensions, and more. Great writing, great drawings, great diagrams. It's great, read it.

[Haskell Programming From First Principles](https://haskellbook.com/) -- They call it "haskellbook" for a reason. It's big, it's rigorous, it's the best intro to Haskell book out there.

[Typeclassopedia](https://wiki.haskell.org/Typeclassopedia) -- all the typeclasses in the "core" Haskell, with their laws and _raisons d'etre_. Great as a reference, satisfying and edifying just to browse through.