# Table of Contents

# Introduction

Category Theory is a mathematical discipline with a wide range of applications in theoretical computer science.
Concepts like *Category*, *Functor*, *Monad*, and others, which were originally defined in Category Theory,
have become pivotal for the understanding of modern Functional Programming (FP) languages and paradigms.
The meaning and applications of these terms in FP can be understood without in-depth knowledge of the corresponding
mathematical definitions and axiomatic. However, a common knowledge of the underlying theory can help FP programmers
understand the design and structure of commonly used libraries and tools and be more productive.

This series of tutorials defines and illustrates the Category Theory concepts which are most widely adopted in FP. We will use simple Scala and pseudocode examples to illustrate the new terms.

# Categories

A **category** is a simple algebraic structure for modelling objects and their relationships.
A category **C** consists of a collection of objects **ob(C)** and a collection of
arrows/morphisms **hom(C)** connecting the objects. In other words, every arrow **f**
can be defined as a pair **[a,b]** of the objects it connects. We write **f: a → b**.

A category also defines an operation for composing arrows, such that for every
**f: a → b** and **g : b → c**, their composition **g ∘ f**
is also an arrow, which connects **a** and **c** - i.e. **g ∘ f: a → c**.

A collection of objects and arrows qualifies as a category only if:

- The composition is associative. More formally,
**h ∘ (g ∘ f) = (h ∘ g) ∘ f**for every three arrows, and; - For every object
**a**there is an identity arrow (i.e. a loop)**i**that connects it to itself:_{a}**i**._{a}: a → a - The identities should have the obvious property that for every
**f: a → b**the following is true**i**. In other words, identities are_{b}∘ f = f = f ∘ i_{a}*neutral*to composition.

## Examples

An intuitive example of a category is the inter-city road infrastructure.
A portion of this category is depicted in the diagram below. In it, the objects are all cities around the world.
We consider two cities to be connected with an arrow if one is reachable from the other.
We assume each city is reachable from itself which is represented with the identity arrows.
If we can travel from city **A** to **B**, and from **B** to **C**,
then we can do so from **A** to **C**. Hence, we can compose arrows.

More generally, every directed graph forms a category whose objects are the graph nodes.
In it, two nodes/objects **a** and **b** are connected with an arrow only if there is
*path* between them in the graph. We also consider that every node in the graph has an arrow to itself - i.e. it is reachable from itself.

In Object Oriented Programming (OOP), a class hierarchy also forms a category.
The category objecta are the types (e.g. classes, traits, interfaces). We consider two
types **A** and **B** to be connected with an arrow if **A** is a subtype of **B**.
These arrows are composable, because if **A** is a subtype of **B**, and **B** of **C**,
then **A** is a subtype of **C**. Finally, each type is a subtype of itself and thus we have
identity arrows as well. This is depicted in the following figure.

## The Hask Category

In Functional Programming, the **Hask** category has a special role.
The objects of **Hask** are all types of the Haskel programming language - i.e. **Ob(Hask) = {Int, String, …}**.
We can generalise that to the types of other languages, like Scala, as well.
For every function converting one type to another, in **Hask** there is an arrow between the two types.
Arrow composition is just function composition. The identity arrows correspond to the identity functions.
The following diagram depicts a portion of the **Hask** category.

# Functors

In category theory, a Functor **F** is a transformation between two categories
**A** and **B**. We write **F : A → B**. **F** must map every
object and arrow from **A** to **B**. In other words, if **a ∈ ob(A)**
then **F(a) ∈ ob(B)**, and if **f ∈ Hom(A)** then **F(f) ∈ Hom(B)**.

We also require that **F** preserves the structure (i.e. identity arrows and composition) of the source category.
More formally:

- If
**f : a → b**is an arrow in**A**then**F(f):F(a) → F(B)**is an arrow in**B**. **F(id**, which means that each identity arrow in_{X}) = id_{(F(X))}**A**is transformed to an identity arrow of the corresponding object in**B**.**F(g ∘ f) = F(g) ∘ F(f)**, which means that the mapping of arrows’ composition in**A**is a composition of their mappings in**B**.

When a functor **F** transforms a category **A** into itself, we call it an *endofunctor* and we write **F:A → A**.

## Functors in FP

Before we delve into Functors and FP, we need to introduce the concept of a *type constructor*.
Essentially, a type constructor is a generic type definition, which takes another type as a parameter.
For example, in Scala **List[T]**, **Vector[T]**, and **Option[T]** are type constructor.
You need to specify the value of the type parameter **T** in order to produce a concrete type.
For example, **List[String]** is a type, while **List** itself is not - it is a type constructor.
We will write **TC[ _ ]** to denote that **TC** is a type constructor.

Functors in Category Theory are a much more general concept than in functional programming (FP).
** All functors in FP are just endofunctors in Hask**. Furthermore, each functor

**F**is associated with a type constructor

**TC[ _ ]**. Each type

**A**in

**Hask**is transformed to

**TC[A]**. For example, if

**TC = List**then

**F: Int → List[Int]**. In other words, the type constructor uniquely defines the mapping of

**Hask**objects.

In order to define a functor, we also need to define the arrow mapping. The arrows in **Hask** are just functions.
Hence, we need to provide a function called **map** with the following signature:
**map: (A → B) → (TC[A] → TC[B])**. For every arrow/function **f: A → B** it
returns its projection/mapping which is also a function - **F(f): TC[A] → TC[B]**.

To summarise, a functor in FP is uniquely defined by a type constructor **TC[ _ ]** and a map function with the aforementioned signature.
The following diagram depicts a functor, whose type constructor is **List[_]**.

## Functors in code

Following the previous definitions, in Scala a functor can be defined as:

1
2
3

trait Functor[TC[_]] {
def map[A,B] (f: A => B): (TC[A] => TC[B])
}

Note that the return type of **map** is a function.
Often the caller just wants to apply/run this function to a given arguement,
instead of passing it on as an arguement or reusing it later on.
Thus, it is convenient to use another analogous definition of a functor, which also applies the resulting function:

1
2
3

trait Functor[TC[_]] {
def map[A,B] (f: A => B)(param : TC[A]) : TC[B]
}

This is essentially a *shortcut* for mapping a function and applying it in one go.
We can also define the **map** function as a method of the type constructor **TC** itself:

1
2
3

trait TC[A] {
def map[B] (f: A => B): TC[B]
}

For simplicity, in this case we can just say that **TC** itself is a functor,
because it is a *type constructor* and has a *map* function. To make it more readable we can just write:

1
2
3

trait Functor[A] {
def map[B] (f: A => B): Functor[B]
}

This trait can then be implemented from all concrete type constructors (e.g. **List** and **Vector**) thus making them functors.

## Examples

In FP, functors are usually applied to map/convert instances of generic data structures
(i.e. type constructors) in a way which preserves their inner structure. For collections
like **List** and **Vector** we would implement the *map* function by just applying it to every element, as in the following pseudocode:

1
2
3
4
5
6
7
8
9
10

class List[A] extends Functor[A] {
// ...
def map[B] (f: A => B): List[B] = {
this match {
case List() => this
case h::t => f(h)::(t.map(f))
}
}
// ...
}

For type constructors which encode *“success-or-failure”* state like **Option** or **Either**
the map function can be applied only if there is a contained value:

1
2
3
4
5
6
7
8
9
10

class Option[A] extends Functor[A] {
// ...
def map[B] (f: A => B): Option[B] = {
this match {
case None => None
case Some(x) => Some(f(x))
}
}
// ...
}

Given that all these functors have a common supertype allows us to write functions which will work with all of them. For example:

1
2

def useAnyIntFunctor(functor: Functor[Int]) =
functor.map(_ + 5).map(_ * 2)

This will work *“as expected”* with all functors - Option, List, etc. However,
in this example the return type is **Functor**, not the actual compile-time type of the parameter.
This can be amended by defining a method type parameter for the arguement’s type.

comments powered by Disqus

Update: updated with comments from Ken Scambler and other collegues from REA