Anatomy of functors and category theory
Menestret Martin ・11 min read
Functional programming atlas (5 Part Series)
[Check my articles on my blog here]
I will try to group here, in an anatomy atlas, basic notions of functional programming that I find myself explaining often lately into a series of articles.
The idea here is to have a place to point people needing explanations and to increase my own understanding of these subjects by trying to explain them the best I can.
I'll try to focus more on making the reader feel an intuition, a feeling about the concepts rather than on the perfect, strict correctness of my explanations.
 Part 1: Anatomy of functional programming
 Part 2: Anatomy of an algebra
 Part 3: Anatomy of a type class
 Part 4: Anatomy of semi groups and monoids
 Part 5: Anatomy of functors and category theory
 Part 6: Anatomy of the tagless final encoding  Yet to come !
What is a functor ?
There's a nice answer by Bartosz Milewski on Quora from which I'll keep some parts:
I like to think of a functor as a generalization of a container. A regular container contains zero or more values of some type. A functor may or may not contain a value or values of some type (...) .
So what can you do with such a container? You might think that, at the minimum, you should be able to retrieve values. But each container has its own interface for accessing values. If you try to specify that interface, you're Balkanizing containers. You're splitting them into stacks, queues, smart pointers, futures, etc. So value retrieval is too specific.
It turns out that the most general way of interacting with a container is by modifying its contents using a function.
Let's try to rephrase that
 Functors represent containers
 For now, we won't care about their particularities, all we need to know is that, at some point, they will maybe hold a value or values "inside" (but keep in mind that every container have particularities, I'll refer to that at the end)
 Defining an generic interface about how to access values inside a container does not make any sense since some containers' values would be accessed by index (arrays for example), others only by taking the first element (stacks for example), other by taking the value only if it exists (optionals), etc.
 However, we can define an interface defining how the value(s) inside containers is modified by a function despite being in a container
So, to summarize, a functor is a kind of container that can be mapped over by a function.
But functors have to respect some rules, called functor's laws...
 Identity: A functor mapped over by the identity function (the function returning its parameter unchanged) is the same as the original functor (the container and its content remain unchanged)
 Composition: A functor mapped over the composition of two functions is the same as the functor mapped over the first function and then mapped over the second one
A quick note about functor / container parallel: the analogy is convenient to get the intuition, but not all functors will not fit into that model, keep it in a corner of you mind so that you're not taken off guard.
How does it look like in practice
Along the next sections, the examples and code snippets I'll provide will be in Scala.
Let explore some examples
We're going to play with concrete containers of Int
values to try to grasp the concept.
val halve: Int => Float = x => x.toFloat / 2
Here we defined the function from Int
to Float
that we are going to use to map over our containers
 Our first guinea pig is
Option[Int]
, which is a container of (0 or 1)Int
.
val intOpt: Option[Int] = Some(99)
val mappedResult1: Option[Float] = intOpt.map(halve)
We can see that an Option[Int]
turns into an Option[Float]
, the inner value of the container being modified from Int
to Float
when mapped over with a function from Int
to Float
...
 Our second guinea pig is
List[Int]
, which is a container of (0 or more)Int
.
val intList: List[Int] = List(1, 2, 3)
val mappedResult2: List[Float] = intList.map(halve)
We can see that an List[Int]
turns into a List[Float]
, the inner values of the container are modified from Int
to Float
when mapped over with a function from Int
to Float
...
 Our third is a hand made
UselessContainer[Int]
, which is a container of exactly 1Int
.
final case class UselessContainer[A](innerValue: A)
val intContainer: UselessContainer[Int] = UselessContainer(99)
val mappedResult3: UselessContainer[Float] = intContainer.map(halve)
We can see that an UselessContainer[Int]
turns into an UselessContainer[Float]
, the inner value of the container being modified from Int
to Float
when mapped over with a function from Int
to Float
... (I've deliberately hidden an implementation detail here for clarity, I'll cover it later)
So we can observe that pattern we described earlier:
A functor, let's call it F[A]
, is a structure containing a value of type A
and which can be mapped over by a function of type A => B
, getting back a functor F[B]
containing a value of type B
.
How do we abstract and encode that ability ?
Functors are usually represented by a type class.
As a reminder, a type class is a group of types that all provide the same abilities (interface), which make them part of the same class (group, "club") of same abilities providing types (see my article about type classes here.
This is the functor type class implementation:
trait Functor[F[_]]{
def map[A, B](fa: F[A], func: A => B): F[B]
}
 The types our functor type class abstract over are type constructors (
F[_]
, our container types)  The type class exposes a
map
function taking a containerF[A]
of values of typeA
, a function of typeA => B
and return aF[B]
, a container of values of typeB
: the pattern we just described.
A note about type constructors: A type constructor is a type to which you have to supply an other type to get back a new type. You can think of it just as functions that take values to produce values. And that makes sense, since we have to supply to our container type the type of values it will "hold" !
Most used concrete type constructors are
List[_]
,Option[_]
,Either[_,_]
,Map[_, _]
and so on.
To illustrate what it means in your Scala code let's make our UselessContainer
a functor:
implicit val ucFunctor = new Functor[UselessContainer] {
override def map[A, B](fa: UselessContainer[A],
func: A => B): UselessContainer[B] =
UselessContainer(func(fa.innerValue))
}
Be careful, if you attempt to create your own functor, it is not enough. You have to prove that your functor instance respects the functor's laws we stated earlier (usually via property based tests), hence that:
 For all values
uc
of typeUselessContainer
:
ucFunctor.map(uc, identity) == uc
 For all values
uc
of typeUselessContainer
and for any two functionsf
of typeA => B
andg
of typeB => C
:
ucFunctor.map(uc, g compose f) == ucFunctor.map(ucFunctor.map(uc, f), g)
However, you can safely use functor instances brought to you by Cats or Scalaz because their implementations lawfulness are tested for you.
(You can find the Cats functor laws here and their tests here. They are tested with discipline.)
Now that you know what a functor is and how it's implemented in Scala, let's talk a bit about category theory !
An insight about the theory behind functors
During this article, we only talked about the most widely known kind of functors, the covariant endofunctors. Don't mind the complicated name, they are all you need to know to begin having fun in functional programming.
However if you'd like to have a grasp a little bit of theory behind functors, keep on reading.
Functors are structurepreserving mappings between categories.
Tiny crash course into category theory
Category theory is the mathematical field that study how things relate to each others in general and how their relations compose.
A category is composed of:
 Objects (view it as something purely abstract, absolutely anything, points for example)
 Arrows or morphisms (which are the ways to go from one object to another)
 And two fundamental properties:

Composition: A way to compose these arrows associatively. It means that if it exists an arrow from an object
a
to an objectb
and an arrow from the objectb
to an objectc
, it exists an arrow that goes froma
toc
and the order of composition does not matter (given 3 morphisms that are composablef
,g
,h
then (h
.g
) .f
) ==h
. (g
.f
))  Identity: There is an identity arrow for every object in the category which is the arrow which goes from that object to itself

Composition: A way to compose these arrows associatively. It means that if it exists an arrow from an object

A
,B
,C
are this category's objects 
f
andg
are its arrows or morphisms 
g . f
isf
andg
composition sincef
goes fromA
toB
andg
goes fromB
toC
(and it MUST exist to satisfy composition law, sincef
andg
exist) 
1A
,1B
and1C
are the identity arrows ofA
,B
andC
Back to Scala
In the context of purely functional programming in Scala, we can consider that we work in a particular category that we are going to call it S
(I won't go into theoretical compromises implied by that parallel, but there are some !):

S
objects are Scala's types 
S
morphisms are Scala's functions Composition between morphisms is then function composition

Identity morphisms for
S
objects is the identity function
Indeed, if we consider the object a
(the type A
) and the object b
(the type B
), Scala functions A => B
are morphisms between a
and b
.
Given our morphism from a
to b
, if it exists an object c
(the type C
) and a morphism between b
and c
exists (a function B => C
):
 Then it must exist a morphism from
a
toc
which is the composition of the two. And it does ! It is (pseudo code): For
g: B => C
andf: A => B
,g compose f
 For
 And that composition is associative:

(h compose g) compose f
is the same ash compose (g compose f)

Moreover for every object (every type) it exists an identity morphism, the identity function, which is the type parametric function:
def id[A](a: A) = a
We can now grasp how category theory and purely functional programming can relate !
And then back to our functors
Now that you know what a category is, and that you know about the category S
we work in when doing functional programming in Scala, rethink about it.
A functor F
being a structurepreserving mapping between two categories means that it maps objects from category A
to objects from category F(A)
(the category which A
is mapped to by the functor F
) and morphisms from A
to morphisms of F(A)
while preserving their relations.
Since we always work with types and with functions between types in Scala, a functor in that context is a mapping from and to the same category, between S
and S
, and that particular kind of functor is called an endofunctor.
Let's explore how Option
behaves (but we could have replaced Option
by any functor F
):
Objects
Objects in S (types) 
Objects in F(S)


A 
Option[A] 
Int 
Option[Int] 
String 
Option[String] 
So Option
type construtor maps objects (types) in S
to other objects (types) in S
.
Morphisms
Let's use our previously defined:

def map[A, B](fa: F[A], func: A => B): F[B]
.
If we partially apply map
with a function f
of type A => B
like so (pseudocode): map(_, f)
, then we are left with a new function of type F[A] => F[B]
.
Using map
that way, let's see how morphisms behave:
Morphisms in S (function between types) 
Morphisms in F(S)


A => A (identity) 
Option[A] => Option[A] 
A => B 
Option[A] => Option[B] 
Int => Float 
Option[Int] => Option[Float] 
String => String 
Option[String] => Option[String] 
So Option
's map
maps morphisms (functions from type to type) in S
to other morphisms (functions from type to type) in S
.
We won't go into details but we could have shown how Option
functor respects morphism composition and identity laws.
What does it buy us ?
 Functors are mappings between two categories
 A functor, due to its theorical nature, preserves the morphisms and their relations between the two categories it maps
 When programming in pure FP, we are in
S
, the category of Scala types, functions and under function composition. The functors we use are then endofunctors (fromS
toS
) because they map Scala types and functions between them to other Scala types and functions between them
In programming terms, (endo)functors in Scala allow us to move from origin types (A
, B
, ...), to new target types (F[A]
, F[B]
, ...) while safely allowing us to reuse the origin functions and their compositions on the target types.
To continue with our Option
example, Option
type constructor "map" our types A
and B
into Option[A]
and Option[B]
types while allowing us to reuse functions of type A => B
thanks to Options
' map
, turning them into Option[A] => Option[B]
and preserving their compositions.
But that is not over ! Let's leave abstraction world we all love so much and head back to concrete world.
Concrete functors instances enhance our origin types with new capacities. Indeed, functor instances are concrete data structures with particularities (the one we said we did not care about at the beginning of that article), the abilty to represent empty value for Option
, the ability to suspend an effectful computation for IO
, the ability to hold multiple values for List
and so on !
Ok, so, to sum up, why functors are awesome ? The two main reasons I can think of are:
 Abstraction, abstraction, abstraction... Code using functors allows you to only care about the fact that what you manipulate is mappable.
 It increases code reuse since a piece of code using functors can be called with any concrete functor instance
 And it reduces a lot error risks since you have to deal with less particularities of the concrete, final, data structure your functions will be called with
 They add functionnalities to existing types, while allowing to still use functions on them (you would not want to rewrite them for every functor instances), and that's a big deal:

Option
allow you to bringnull
into a concrete value, making code a lot healthier (and functions purer) 
Either
allow you to bring computation errors into concrete values, making dealing with computation errors a lot healthier (and functions purer) 
IO
allow you to turn a computations into a values, allowing better compositionality and referential transparency  And so on...

I hope I made a bit clearer what functors are in the context of category theory and how that translates to pure FP in Scala !
More material
If you want to keep diving deeper, some interesting stuff can be found on my FP resources list and in particular:
 Scala with Cats  Functor chapter
 Functors' section of the awesome Functors, Applicatives, And Monads In Pictures article
 Yann Esposito's great "Category theory and programming"
 Let me know if you need more
Conclusion
To sum up, we saw:
 That a functor is a kind of container that can be mapped over by a function and the laws it has to respect
 Some examples and identified a common pattern
 How we abstract over and encode that pattern in Scala as a type class of type constructors
 We had a modest overview about category theory, what functors are in category theory, and how both relates to pure FP in Scala
 We concluded by how great functors are and for what practical reasons
I'll try to keep that blog post updated.
If there are any additions, imprecision or mistakes that I should correct or if you need more explanations, feel free to contact me on Twitter or by mail !
Edit: Thanks Jules Ivanic for the review :).
Functional programming atlas (5 Part Series)