If you are a former Java developer and have become a Scala fanboy like me, you will probably sooner or later encounter terms like monad, functor or other mysteries from the realm of category theory which make you feel like a little dummkopf (screamingly funny for a German like me, according to www.dict.cc this seems to be a proper English verb. If you already feel comfortable with these, don’t waste your time and move along. But if not, I would like to invite you to a little sightseeing trip that reflects my efforts to get to know this secret realm somewhere in between abstract mathematics and computer science.
This blog post is meant to be an introduction. Depending on the effect on my health (while writing I’m often afraid that my head might explode), my future spare time (understanding comes very slowly, if at all) and your feedback, I am going to write a followup. But for now let’s get started.
What’s a category?
Obviously this should be the first question when talking about category theory, although in my opinion the concept of a category is not too useful for programming. Here comes a comprehensive answer:
A category is made up from objects and maps (aka morphisms or arrows) between these objects. Maps can be composed in an associative fashion and for each object there is an identity map which is neutral with regard to composition.
Objects can be anything, but let’s look at a simple case: The category of finite sets. The diagram below depicts two such finite sets as well as a map from the one called source (aka domain) to the other called target (aka codomain).
A little more formally, we can call the domain A
and the codomain B
and write the map like this:
1


Now what’s composition? Let’s look at the next diagram, where I added another finite set and another map. Please don’t worry that in this strange world eating habits are different from what you might know ;–)
Let’s call the new set C
and the new map g: B → C
. Obviously we can get from A
to C
by first following f
and then g
. Therefore we get a new map from composing f
and g
:
1


Now that we know composition, we have to talk about associativity and identity. Let’s add another map h: C → D
. Then the associativity law requires the following to hold true:
1


Associativity should become clear pretty fast from thinking of addition or multiplication of numbers. Therefore let’s move along towards the identity laws. These require that for each object X
of the category there is an identity map 1_{X}: X → X
which satisfies the following rules:
f ο 1_{A} = f
1_{B} ο f = f
The following diagram depicts an identity map in our example category of finite sets. Obviously for identity maps the domain and codomain are the same object.
OK, that’s it. That’s categories. Objects, maps, composition, associativity and identity. If you would like to dive a little deeper into the theory, I recommend Wikipedia or “Conceptual Mathematics” by Lawvere and Schanuel. I will move along and look at categories from a Scala point of view.
Categories in Scala
Note: In the following I will borrow a lot of ideas and even some (slightly modified) code from the awesome scalaz project. This Scala library, together with the Runar’s blog, provides an incredibly valuable source of information and inspiration about advanced functional programming in Scala.
Now that we have investigated the category of finite sets, let’s implement another one in Scala. Therefore we consider the category made up from Scala types as objects and Scala functions as maps. We still have to prove that this is a category, but first let’s code it up:
1 2 3 4 5 

OK, it looks like we have all the ingredients we need: Types are objects, functions with one argument (trait Function
) are maps, id
returns the identity function for each A
and compose
composes two functions.
It looks obvious, that the associativity and identity laws are satisfied, but better let’s check using a simple unit test written using the awesome specs and ScalaCheck frameworks:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 

OK, so now we know that Category
indeed adheres to the category laws. But that’s not the end of our story! Let’s move along to a more general category in Scala: While sticking to the Scala types as objects we will use the type constructor * >> *
for the maps.
1 2 3 4 

Please note, that A >> B
is just another way to write >>[A, B]
, which nicely reflects the fact that we are talking about maps here.
Of course our Category
is an implementation of this GenericCategory
:
1 2 3 4 5 

If you are interested in further types of categories, don’t hesitate to take a look at scalaz: You can find numerous categories there, e.g. a category of partial functions or a monoid category. I will keep it that way and move along to another important concept in category theory.
Functors
Now that we know categories and how to represent certain ones in Scala, let’s look at another important concept of category theory, which is also very important for functional programming. Consider two categories C1
and C2
; then a functor F
is a structurepreserving mapping between these categories.
OK, but what does that mean? A mapping between categories simply means that
 every object
A ∈ C1
is mapped to an objectF(A) ∈ C2
and  every map
A → B
between two objectsA, B ∈ C1
is mapped to a mapF(A) → F(B)
between two objectsF(A), F(B) ∈ C2
.
In order to preserve the category structure this mapping must preserve the identity maps and the compositions. More formally:
F(1_{A}) = 1_{F(A)} ∀ A ∈ C1
F(g ο f) = F(g) ο F(f) ∀ f: A → B, g: B → C where A, B, C ∈ C1
Before thinking about the “meaning” of a functor, let’s code it up in Scala using our GenericCategory
(of Scala types and arbitrary maps between these) as foundation:
1 2 3 

Again, >>
and >>>
as well as F
are type constructors. Looking at the ingredients, we find all that we need: Types A
and B
are mapped to types F[A]
and F[B]
and maps A >> B
are mapped to maps F[A] >>> F[B]
.
Now let’s move along from arbitrary maps to Scala functions, i.e. choose our Category
as source and target of the functor. This results in a so called endofunctor (same source and target) and looks like the following:
1 2 3 4 

Please note, that the new fmap
method is just for convenience and delegates to the inherited one. Using the higher kinded type for the first parameter list makes it possible to infer the type of A
for the function in the second parameter list.
In order to code up some examples, we have to specify the type constructor F
. Let’s start with good old List
:
1 2 3 

This one let’s us map a function over a List
, which means that this functor looks like a container that allows us to apply a function to all of its elements. This is a very intuitive way to think about functors. And it makes clear, that functors are a very important concept for functional programming, because if you look at the collections of the Scala library, you will see, that all of them provide this “mapping a function over the elements”.
OK, let’s see how we can use that. Therefore we add a Functor
object, move our ListFunctor
into that and make it implicit and add a generic fmap
method:
1 2 3 4 5 6 7 8 9 10 

Welcome type classes! The new generic fmap
method takes an additional and implicit parameter of type Functor
parameterized with a higher kinded type. When we call this method with an instance of this higher kinded type and a function but no functor, the compiler will look for a matching implicit value. Let’s see it in action:
1 2 3 4 5 

While we could have reached the same result by simply calling map
on the List
instance, we now have something more general: A fmap
method that works for any type for which we provide a functor.
We still have to verify that our ListFunctionFunctor
satisfies the functor laws. Hence we write another unit test:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 

Fine! Now let’s look at another example. Why not use Option
as type constructor for the Functor
trait?
1 2 3 4 

This one let’s us map a function over an Option
, which can be thought of as applying the function in the context of the Option
. If it is None
, the function won’t be applied, if it is Some
, it will be applied. This “computational context” is another way of looking at functors which sometimes is called “lifting” of functions: The function is lifted from its normal context to the functor’s context.
Let’s code up another example that makes this interpretation even more obvious. Now we use Function0
as type constructor for the Functor
trait:
1 2 3 4 

Let’s see this one in action:
1 2 3 4 5 6 7 8 

As you can see, the function f
is lifted into the context of the given Function0
, i.e. it works on the output of that.
Conclusion
In this blog post we looked at two basic objects from category theory: Categories and functors. Of course there are others, some of them heavily used (e.g. monads), but I will keep it like that for now. Hopefully I could show you that category theory offers some interesting and valuable concepts that can be applied to and expressed in Scala. As I consider myself still a rookie in category theory, I’d be happy to get your feedback.