Functors : Category Theory Stuff
If you ever want to talk the same language as smart Haskellers, you need to know a bit of category theory. Here’s some notes on how I understand category theory right now.
The first thing to to appreciate is a list isn’t a functor, “list” is a functor. In particular, it’s a mapping from one type to another e.g. int to list of int. Furthermore, it’s a mapping that preserves the structure of int, in that performing “map” works.
Considered this way, there’s no such thing as a “higher order type”, there’s just functions from one type to another. Types with more than one type parameter in Java/C# are just multiple arity functions on types.
Some other things that are worth considering: you can make a list of any type, even a list. Not only that, but if a and b are different types, list of a and list of b are different as well. So, in maths terms, it’s an injection of the type space onto a subsection of the same type space.
What the heck is a category?
Now, let’s go back to the start and talk terminology. A category is a bunch of “objects” and “arrows” between them. They behave basically like values and functions. Indeed, values and functions form a category. The only real requirement is that arrows compose like functions and that there’s an identity map that does nothing.
In the context of type theory, the objects are the types themselves. The arrows are higher order type constructors. Just like normal functions, they’re not reversible. Now let’s make a bit weirder. Just the lists and the functions between lists and other lists form a category too.
The next bit may or may not make sense if you don’t have a maths background. Mathematically, a functor isn’t anything to do with types at all, it’s just a mapping between one category and another that preserves some structure.
Let’s think of a really simple category. Let’s have the objects be integers and the arrows be rotations of integers e.g. add three, subtract two. And “add zero” is an identity map.
Now let’s have another one which is the same, only all of the numbers and rotations are even. Then “times two” maps objects and functions between the two categories. So 3 becomes 6 and “add 3” maps to “add 6”. And finally, “add zero” becomes… “add zero”. So “times two” is a perfectly valid functor that is absolutely nothing to do type theory at all.
Finally, a small note, if you’re just looking at category theory for the purposes of understanding Haskell you’ll come across the phrase “locally small” a lot. Every last category you are ever going to worry about is locally small, so don’t sweat it.