what is a functor

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 documentationFunctors 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.