Introduction to Category Theory
In our previous articles, we discussed the significance of functional composition in functional programming, and provided an example of how it can result in code that is easier to test and maintain. However, what happens when two functions cannot be composed? How can we overcome this issue? Fortunately, many researchers and mathematicians have dedicated themselves to developing a theory focused on composability: Category Theory.
Category Theory is a branch of mathematics that provides a way to study and understand the structures and relationships between different mathematical objects in a very general and abstract way. It does this by looking at the patterns and connections between these objects and their transformations.
Category Theory was founded by Saunders Mac Lane and Samuel Eilenberg in 1945.
Definition
A category is a pair (tuple) of (Objects, Morphisms)
where:
Objects
is a collection of objectsMorphisms
is a collection of morphisms (also called “arrows”) between objects
Please note that the term object has nothing to do with the objects in the context of software engineering and programming. You can think these
Objects
as black boxes that we can’t know what’s inside.
For every Morphism
there is a source Object
A
and a target Object
B
.
We write f: A ⟼ B
and we say that “f is a morphism from A to B”.
There is also, an operation, ∘
, called “composition”, such as the following properties hold true:
 Composition of morphisms: Given the following morphisms
f: A ⟼ B
andg: B ⟼ C
then there has to be a third morphismg ∘ f: A ⟼ C
which is the composition off
andg

Associativity: if
f: A ⟼ B
,g: B ⟼ C
andh: C ⟼ D
thenh ∘ (g ∘ f) = (h ∘ g) ∘ f

Identity: for every object X, there is a morphism called identity:
X ⟼ X
such as for every morphismf: A ⟼ X
andg: X ⟼ B
, the following equation holds trueidentity ∘ f = f
andg ∘ identity = g
.
Category Theory in Software Engineering: Modeling programming languages with categories.
A category can be seen as a simplified model for a typed programming language, where:
Objects
are types.Morphisms
are functions.∘
is the usual function composition.
Lets consider the following Category
:
Given that:
A
= stringB
= numberC
= booleanf
= string => numberg
= number => booleang ∘ f
= string => boolean
The implementation of this category in typescript would be the following:
const idA = (value: string): string => value;
const idB = (value: number): number => value;
const idC = (value: boolean): boolean => value;
const f = (s: string): number => s.length;
const g = (n: number): boolean => n > 0;
const gf = (s: string): boolean => g(f(s));
Composition’s core problem
In programming, we can compose two generic functions, f: (a: A) => B
and g: (c: C) => D
, as long as C
is equal to B
. However, what if B
is not equal to C
? How can we compose two functions in such a scenario? Is giving up the only option?
In the next article we’ll see under which conditions such a composition is possible. We will also explain the concept of a Functor
, an Applicative Functor
and a Monad
.
Resources: