Category Theory in Haskell
Introduction to Category Theory
Dots and Arrows
Category theory is a way of looking at mathematics that focuses on relationships rather than details. Instead of worrying about what things are, we focus on how they connect to each other. At its core, it's a theory of dots and arrows.
The dots are called objects, and the arrows are called morphisms. An object can be anything: a number, a set, a shape, or even another category. A morphism is a connection or transformation between two objects. It always has a source object (where it starts) and a target object (where it ends).
So, a category is just a collection of these objects and morphisms. But for a collection to be a true category, it must follow two simple, powerful rules.
A category consists of objects and morphisms (arrows) that describe relationships between these objects.
These rules govern how the arrows behave, ensuring the whole system is consistent and predictable.
The Two Simple Rules
The first rule is about connecting arrows. It's called composition. If you have a morphism from object A to object B, and another from object B to object C, then there must be a direct morphism from A to C. It’s like taking connecting flights. If you can fly from New York to Chicago, and then from Chicago to Los Angeles, you have effectively traveled from New York to Los Angeles.
This new, direct morphism is called the composite. If the first arrow is and the second is , their composite is written as . You read this backwards: "g after f". This is because in mathematics, we often apply functions from right to left.
The second rule is about doing nothing. Every object in the category must have a special morphism called an identity morphism. This is an arrow that starts and ends at the same object. For an object A, its identity morphism is written as .
Composing any morphism with an identity morphism doesn't change it. If is an arrow from A to B, then connecting it with the identity at A or the identity at B just gives you back . It's like standing still before or after taking a step; your position change is still just that one step.
And that's it. A collection of objects and morphisms that satisfies these two rules, composition and identity, is a category. This simple structure is surprisingly powerful and appears all over mathematics and computer science.
Examples of Categories
The abstract definition can feel a bit airy. Let's ground it with some concrete examples.
Set: This is the most common example. The objects are sets (like
{1, 2}or{a, b, c}). The morphisms are functions between sets. Composition is just function composition, and the identity morphism is the identity function that maps every element to itself.
But categories can be much simpler. Imagine a category with just one object and one morphism: the identity morphism. That's a valid category. Or consider a category representing a single ordered relationship.
| Category | Objects | Morphisms |
|---|---|---|
| Types | Data types (e.g., Int, String) | Functions between types (e.g., (Int) -> String) |
| Order | Numbers (e.g., 1, 2, 3) | An arrow from to if |
| Monoid | A single object, let's call it * | The elements of the monoid |
In the Order example, if we have a morphism from 2 to 5 (since ) and one from 5 to 10 (since ), composition guarantees a morphism from 2 to 10 (since ). The identity morphism exists because every number is less than or equal to itself ().
These building blocks, objects and morphisms, form the foundation for understanding more complex ideas. The focus is always on structure and how things compose, not what they're made of.