1 2025/categories-0711 Crash course on category theory stuff I guess. I assume some basic background, but it should be enough to 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
For example, in the Cartesian closed category of
curry :: ((a, b) -> c) -> a -> b -> c
uncurry :: (a -> b -> c) -> (a, b) -> cInt, 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 functions,
whereas the objects are the Haskell types themselves, not specific instances of that type.
Think back to the analogy for
Drawing parallels to a -> b itself is a type in Haskell (the type of functions from a to b),
a -> b type is more or less the hom-set
In addition to having these mappings between two different categories, we are also allowed to have mappings from a category to itself! These are called endofunctors, and of course monads are monoids in the category of endofunctors so we have to understand these.
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 f :: a -> b. Note that with
fmap we are talking about List f (thats not valid Haskell but you get it) and not List (a -> b), which is dealing with the
type a -> b and not the morphism f.
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, 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:
join :: Monad m => m (m a) -> m a
return :: Monad m => a -> m aHere, join simply flattens the list, 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 mapping 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.
It would build this Maybe Int using return, and if we wanted to manipulate the Int inside the Maybe
we would use fmap f where f is some function that takes Ints. But what if
f is another function that might fail? Then fmap f result would be a Maybe Maybe Int,
which is not ideal, so we can use join to turn the Maybe Maybe Int back to a Maybe Int.
This idea of join (fmap f result) is of course monad bind, result >>= f. However,
I like Kleisli composition (<=<) better than bind because it’s more symmetric,
so I will use that:
(>>=) :: Monad m => m a -> (a -> m b) -> m b
(<=<) :: Monad m => (b -> m c) -> (a -> m b) -> a -> m c
(.) :: (b -> c) -> (a -> b) -> a -> cNotice how (<=<) (which can be implemented from fmap and join) mirrors the normal function composition (.).
This means that we have the following monoid properties:
return <=< f = f -- Left-identity
f <=< return = f -- Right-identity
(f <=< g) <=< h = f <=< (g <=< h) -- AssociativityWe have a monoid! I don’t think this is the famous monoid in the category of endofunctors though, we have to go through natural transformations for that.
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.
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.
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 unreachable branch of code. 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 control flow never exits from the other side of the Err(_) branch,
the compiler can give it a type of ! because it will never face the paradox
of making a value of !. Other expressions can also be !, like panic! and loop {}.
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 {}
}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
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 some_list :: List List List a
and other_list :: List a:
join (fmap join some_list) = join (join some_list) -- Left square (associativity)
join (fmap return other_list) = join (return other_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.
Ok I still genuinely have no idea how this works at this point. Someone please explain to me.
Generalization of elements in a set and instances of a type: each “element” of an object
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