This article aims to serve as a gentle introduction to abstract algebra and category theory concepts for engineers, with examples in the Scala programming language. Firstly, we will review some of the major properties in Scala’s type system that allow category theory to be implemented. Then we will review the formal definitions of Monad and Functor and its implementations in Scala.
I will start by reviewing on of the features that make Scala’s one of the most advanced and powerful type systems. In my humble opinion, this feature should be the starting point for programmers that want to learn category theory, since it by its means that monads and functors can be implemented.
Higher-kinded types is an abstraction over types. As Adriaan Moors clearly explains in this post, higher-kinded types are easier to understand if seen as a higher-order polymorphism. This can be shown in the following example:
The second and third classes illustrate its purpose. The class Foo takes as parameter a type constructor taking one parameter, while Bar takes as parameter a type constructor taking two parameters.
This (seemingly) simple feature allows us to develop powerful abstractions (not only over types, as classic java polymorphism, but over type constructors), and gives birth to advanced and complex abstract algebra libraries that we will cover in the next sessions.
More information about Higher-kinded types can be found in this twitter blog and in this wonderful TypeLevel post.
Before going any further, lets review the formal definition of category.
A category consists of:
- a set of objects
- for each pair a set of morphisms (or arrows, or maps) or
- for each triple a binary operation noted as , also referred as composition of morphisms
subject to the following conditions:
- composition of morphisms is associative:
- for every element there exists a morphism such that and
In simple words, in software engineering we could see categories as a way to represent objects and the relations that link them (the morphisms).
But what about the mappings (or relations, or morphisms) that link one category to another?
This crazy idea would kinda like if we wanted to have a second degree of generics ;)
Well, actually Scala allows this, and calling it “generics of a higher kind” would not be a huge mistake. As presented in the introduction, we can have higher kinded types that could mimic the relationship between categories.
Firstly, lets review the formal definition of a functor.
Given categories and , a functor from to :
- maps each element to an element in
- maps each morphism in to a morphism in
- for every element
- for all morphisms and in
For us, software engineers, this means that a functor is just a morphism between categories, also called structures preserving map. Basically, a functor would just define a
This is the functor definition in scalaz:
and in cats:
Similar to the functor, the monad is an abstraction for an operation. But instead of the map, it is an abstraction of the flatMap operation.
Havin this abstraction is of a huge importance. Since monadic structures provide us with the ability to wrap context information, and eventually return a subset of the parent type.
As shown above, the
flatMap operation returns a subset of the parent type M[_]: M[B].
The importance of this category relies also in that many of the data structures we are used to in functional programming have monadic properties; like
We have reviewed some of the most basic but also most important concepts in abstract algebra used in category theory.
These mathematical frameworks provide us (engineers) with useful tools in our continuously pursuit of abstraction, factorization and readability in code.