## Quick intro to categories

Category theory is a topic from pure math but don’t fear – the basic stuff is not that hard to grasp.

And the domain (Types in programming languagues or Haskell in this case) should be well known to us

developers.

### Basic definition

A category \(\mathcal{C}\) consists of two collections (or classes) of stuff: *Objects* \(Obj_{\mathcal{C}}\) and *Arrows* \(Hom_{\mathcal{C}}\).

For a first intuition it might be benefical to just think of objects as just *mathematical sets*

and *arrows* as just mathematical mappings (functions).

To make it a bit easier to read we will use upper-case letters like \(A\), \(B\) and \(C\) for objects and lower-case letters like \(f\), \(g\) and \(h\) for arrows.

You know it’s math so those classes will come with a few extra stuff and their elements have to fullfill some laws (I will stop to write the category in there for now – it’s always the same):

- Every Arrow \(f\) is given a
*domain*\(dom(f) \in Obj\) and*codomain*\(codom(f) \in Obj\) and we write a short-form of this as \(f: A \rightarrow B\) if \(f\)s domain is \(A\) and its codomain is \(B\). Often the collection of all arrows from*domain*\(A\) to*codomain*\(B\) is written as \(\mathcal{C}(A,B)\). - There is an
*operation*\(\circ\) you we can use to compose two arrows: if we have \(f: A \rightarrow B\) and \(g: B \rightarrow C\) we get another arrow \(g \circ f: A \rightarrow C\). - There is a special arrow \(id_A: A \rightarrow A\) for each object \(A\). And yes – this will be just what you think it is.
- Here are the laws: for all arrows you have \(f \circ (g \circ h) = (f \circ g) \circ h\) and \(f \circ id = id \circ f = f\) (and yeah you have to choose the right domains/codomains and even the \(id\) functions used there will be two different ones for this to work out – you can try this as an exercise or just read on and do it as an exercise in Haskell)

Chances are good, that this all looks very familiar to you. Indeed not only do *arrows* look like functions between set, the collection of all sets and the functions between them form a category \(\mathcal{Set}\).

## Categories in Haskell

Now we want to transfer this into Haskell-World: We can get a category (usually called \(\mathcal{hask}\)), where the *objects* are the haskell-types (`Int`

, `[Char]`

, `Maybe Float`

, `Int -> Int`

, whatever) and the *arrows* are just your usual haskell functions.

Easy isn’t it? It’s just new names for your stuff ;)

## What is a *functor*

Now we climb the ebony-tower one more level: we look at the **structure-preserving**-maps between categories – and yes those we will call **functors**.

So what exactly does *structure-preserving* mean here?

Well for a *functor* \(\mathcal{F}\) between two categories \(\mathcal{C}\) and \(\mathcal{D}\) we need two mappings: one that maps *objects* in \(\mathcal{C}\) to *objects* in \(\mathcal{D}\) and one that will map their *arrows* so that *domains*, and *codomains* match.

We will be lazy here and just use the same symbol \(\mathcal{F}\) for both of them.

So we have $$\mathcal{F}: Obj_{\mathcal{C}} \rightarrow Obj_{\mathcal{D}}$$ and

$$\mathcal{F}: Hom_{\mathcal{C}} \rightarrow Hom_{\mathcal{D}}$$

*Structur-preserving* now just means that everything has to fit:

Imagine you have an arrow in \(\mathcal{C}\): \(f: A \rightarrow B\). For \(F(f)\) we demand that

$$

F(f): F(A) \rightarrow F(B)

$$

that is the functor maps the domain and codomain just right.

Of course the composition needs to be compatible as well – meaning

$$

\mathcal{F}(f \circ_{\mathcal{C}} g) = \mathcal{F}(f) \circ_{\mathcal{D}} \mathcal{F}(g)

$$

(Note that there are two different compositions involved here).

## And what about Haskell?

Well in Haskell we cannot just use the same symbols for different stuff – and indeed this was something

I first struggled with a bit. So I hope to make this clear here.

We already saw that the objects are just types, and now we need *something* to map types to types.

Type-constructors with kind `* -> *`

do just this.

That would include `Maybe`

, `[]`

, … – and yes these are the things we call **functors** in Haskell.

Remember: there is a type-class called `Functor`

in Haskell defined like this:

class Functor f where fmap :: (a -> b) -> f a -> f b

(There is another operator, defined with fmap in there that is not important for us here).

If you look carefully you see that `fmap`

seems to be just what we need for our second mapping – the one that takes *arrows* to *arrows* (or functions to functions for us).

Maybe you did not see it till now – but we did not really change the categorie we are working in. Those

functors don’t change the category they go from \(\mathcal{hask}\) to \(\mathcal{hask}\) – in math these are called *endo-functors*.

### What about the laws?

If you have a look at the documentation – `Functors`

in Haskell should obey these laws:

fmap id == id fmap (f . g) == fmap f . fmap g

Look closely – these are exactly the laws the *categorial functors* need to obay for \(\mathcal{hask}\).

Of course your usual instances of `Functor`

all obey these laws – but they are not

checked by the compiler. So you have to be carefull when writing new functors.

## What about other languagues

As you might know I work in .net/F#/C# in my day-job. It has no type-classes and so there nobody really

talks about functors there – but of course they are there.

F#s `Option`

, most collection types with LINQ and so forth all have what you need for it.

Yes there is no common `fmap`

but you have `Option.map`

and `List.map`

and of course LINQs `.Select`

.

And the mapping between the types is just done through generics.