0 2025/categories-0711 Crash course on category theory stuff I guess.
I assume some basic background, and will not be explaining Haskell or Rust concepts in depth. You can read Learn You A Haskell for an intro to Haskell. You should also know that a monoid is a set with an associative binary operation and an identity element.
A category is a collection of objects and morphisms between objects (like a directed graph).
The objects in a category generalize some algebraic structure, while morphisms generalize functions
between these structures. For example: we can have
Note: Don’t be tempted into thinking that sets are categories (or later that types like Int and
Bool are categories). We take the perspective that these things (sets and types) are the
objects in the category we are dealing with, NOT the elements of the set or specific instances
of a type.
We can concretely represent a morphism between two sets
Int, Bool, etc.) and the morphisms are normal Haskell functions. Here, we can think of the types
as being sets of all the instances of that type. For example, we can say
Int = {0, 1, 2, 3, ...}
Bool = {True, False}
...A point of confusion here for me was that a morphism is a specific Haskell function.
On the other hand, the objects are the Haskell types themselves, not specific instances of that type.
Think back to the analogy for
Because we can build this representation of
In addition to having these mappings between two different categories (
Remember the Cartesian product from (x, y).
Being a typesystem, x -> y
to denote the type of functions from type x to type y.
In this way, morphisms in
curry :: ((x, y) -> z) -> x -> y -> z
uncurry :: (x -> y -> z) -> (x, y) -> zMr. Haskell Curry must be proud. Currying is the relationship that any 2-argument function is equivalent to some 1-argument function that returns another 1-argument function (and vice versa).
Bonus tidbit: Category theorists would call the type y -> z an exponential object in curry g:
Now back to endofunctors! One example of an endofunctor is List:
it takes any type a to the type List a, which is obviously
just a list of as. Since we are mapping from a type to another type,
this is an endofunctor from the category of fmap is exactly this mapping:
fmap :: Functor f => (a -> b) -> f a -> f bfmap simply applies the endofunctor (e.g. List) to a morphism like do_something :: a -> b. Note that with
fmap, we are talking about List do_something (that’s not valid Haskell but you get it) and not List (a -> b), which is dealing with the
object a -> b (the type) and not the morphism do_something (the actual function).
Remember currying: we want to interpret fmap as a function that takes in a function and returns a new
function that acts on lists rather than raw as and bs. The alternative interpretation
is that fmap takes in two arguments: a function to map over a list and a list to map over,
returning the result of applying that function over the list. However, this interpretation
is less useful when we’re thinking about monads.
To make List into a monad, not just an endofunctor (a monad is like a subclass of endofunctors),
we need additional structure in the form of a
multiplication join and return respectively. Technically,
wikipedia
defines these as natural transformations (“morphisms of functors”) but we can
do the same thing without opening that can of worms (for now):
join :: Monad m => m (m a) -> m a
return :: Monad m => a -> m aHere, join simply flattens the list by one level, and return returns a singleton list
with one element (whatever we pass into it). Note the difference between List itself
and return: List is a functor acting on Haskell types and Haskell functions (morphisms),
while return is a morphism that maps specific instances of Haskell types to instances of the list type.
The purpose of these operations is probably better understood with the most famous monad: Maybe. A Maybe
is like a List that can have 0 or 1 elements: it can be either a Nothing, or a Something value.
In functional programming, instead of using exceptions, we may want to make
a function return something like a Maybe Int when it might fail. For example,
it might return Something 2 when it succeeds, or a Nothing when it fails. Let’s look at an example of join:
-- these functions can make `Maybe Int`s by using Maybe's `return`.
func_might_fail :: Int -> Maybe Int
compute_something :: Int -> Maybe Int
result = func_might_fail 2
-- this is the same thing as writing `result >>= compute_something`, where >>= is monad bind.
final_result = join (fmap compute_something result)Here, we have two functions that might fail: func_might_fail and compute_something. We
wanted to compose them together, but we ran into the problem that fmap compute_something (func_might_fail 2)
would be a Maybe Maybe Int. Thankfully, join can take us back to a Maybe Int by erasing information
about where specifically our operation failed: we can no longer distinguish between an error in func_might_fail
(where we get Nothing) and an error in compute_something (we get Something Nothing).
With this, we can define a really nice operation for composing these functions called Kleisli composition:
(>>=) :: Monad m => m a -> (a -> m b) -> m b
-- (g <=< f) = \x -> join (fmap g (f x))
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
(.) :: (b -> c) -> (a -> b) -> a -> cNotice how (<=<) mirrors the normal function composition (.).
This means that we have the following monoid properties on the functions f, g, and h:
return <=< f = f -- Left-identity
f <=< return = f -- Right-identity
(f <=< g) <=< h = f <=< (g <=< h) -- AssociativityWe have a monoid! This isn’t exactly the famous monoid in the category of endofunctors though, but I’ll explain that after we cover natural transformations.
Bonus fun fact: functions are monads too! Consider (a ->). Here fmap is just normal function composition (.),
return builds a constant function, and join just feeds in the input value twice to unwrap
the inner function.
Natural transformations are mappings between two functors. These two functors
must have the same signature (map between the same two categories
Just as morphisms in
Now we can understand how the monad unit return morphisms, one for every object (every type in join morphisms. This new perspective is useful
for talking about the category of endofunctors in
This is even more abstract nonsense but here goes! A monoid in category theory is slightly different
from the familiar definition of a set with an associative binary operation and a unit. In category theory,
a monoid is an object
Notice how this exactly lines up with our monad
But there’s also a subtle problem in our initial definition of a monoid: morphisms must be between objects of the same category,
so for us to have a
In the category of endofunctors, this List monad) is an endofunctor, so is List List), so in
the category of endofunctors we can have a morphism
But this raises a natural question. Our usual definition of a monoid dealt with a binary operation
on the elements of the monoid object in the category theoretic definition of a monoid.
So what are the “elements” of the
An element obj :: a corresponds exactly
with a function f () = obj, where f :: () -> a. In Haskell, the type () is the equivalent of a singleton set:
it is the unit type with exactly one inhabitant (there is only one value it can have, and the value
is also called ()).
I don’t think there is a generalized way to determine what object we should choose (the equivalent
of a singleton set or unit type)
as the object to define what an “element” is, and honestly idk what the correct choice is. I actually don’t
have an answer for this so let’s just mess around.
Say we choose the identity functor
Here’s the detail of how to find the “element” of
You did it! Now you understand why a monad is a monoid in the category of endofunctors! But we can go deeper into category theory land…
Let’s make sense of this commutative diagram from the category theory definition of a monad:
Here, I write List
endofunctor 3 times. Remember that join morphisms we just saw, and it is specifically
join :: List List X -> List X, flattening a list of fmap of this function, and from here you can probably figure out
what the rest means (some of them replace the subscript X with List X).
These two squares boil down to these two equations on triple_list :: List List List a
and single_list :: List a:
join (fmap join triple_list) = join (join triple_list) -- Left square (associativity)
join (fmap return single_list) = join (return single_list) -- Right square (identity)(This probably doesn’t work in real Haskell since it wouldn’t know
you want the List monad’s return, but you get the point.) Now we
can write the same two commutative squares, but this time in the category of
endofunctors on
Ok, so applying
This is equivalent to fmaping with the
Alternatively, we can have a functor
This is a natural transformation on a type of all the join :: List List a -> List a morphisms in another List and treats
b = List a as the new black-box type so we have join :: List List b -> List b. The same thing happens for return.
Thus, whiskering and horizontal composition utilizes the composition of the underlying functors acted on by the natural transformation, and you should be able to convince yourself that the two versions of the monad commutative diagrams are the same.
One of the really cool things you get when looking at a typesystem from a category-theoretic point of view is the concept of initial objects and terminal objects. These concepts are dual to each other (you reverse the arrows in the commutative diagrams), so let’s look at them one at a time.
A terminal object is an object where every other object has exactly one morphism to the terminal object.
In Rust, the terminal object is the type ().
The terminal object is a type with exactly one inhabitant, so we can think of the terminal object as a singleton set.
Since there is only one possible value it can have, the only possible function you can write is returning that value,
so there is a de facto way to convert every other type to a ().
An initial object in a category is an object for which there is exactly one morphism to every
other object. In Rust, the initial object is a type called Never, or !. Because there is only one morphism
from ! to every other type, there is an unambiguous way to convert ! to any other type.
But what is !? Now things get interesting.
I’m going to work backwards and reveal the “implementation details” of the initial object first
before going back and deriving the desired properties.
! is a type with no inhabitants, i.e. it cannot be instantiated. You can think of it as
enum Never {}; // this is !It is an empty set, and while you can never have a value of type !, you can talk about the type ! itself.
But then how is that useful at all?? Well, ! is the type of an expression that can never be materialized.
Expressions like loop {}, panic!, and return have type !.
To see what I mean, consider the following Rust example:
fn do_something(_: i32) -> Result<i32, Error>;
fn do_other_thing(_: i32) -> ();
fn f(x: i32) -> Option<i32> {
let y: i32 = match do_something(x) {
Ok(v) => v + 5, // this is i32
Err(_) => {
println!("Oh no!");
return None; // `return` has type !, which can be converted to anything
}
}; // overall, y is still i32 since we can convert the !
do_other_thing(y);
Some(y * 6)
}Of course, this example is an implementation of the ? operator. Because of the semantics of a Rust match,
the Err(_) branch of the code is basically running let y: i32 = return None; at the end of the day. Yet,
because return is ! and ! is the initial object, y really is an i32.
Control flow never exits from the other side of the Err(_) branch after the return,
and the compiler can use ! because it will never face the paradox
of making a value of !.
So why does this mean there’s exactly one morphism from ! to every other type?
Remember the formal way we represented morphisms in
enum Never {};
fn coerce<T>(x: Never) -> T {
match x {}
}The category of finite-dimensional vector spaces is cartesian closed too. Objects are vector spaces, and morphisms are linear transformations between vector spaces. Since you can take a linear combination of linear transformations and have another linear transformation (i.e. matrices are vectors too, with addition and scalar multiplication), morphisms in the category of vector spaces are also objects in that category.
Because of scalar multiplication,
we can also think of vectors as morphisms/linear transformations