Functors
As can be imagined after the last article, categories in and of itself are not particularly useful. What's missing is a way to 'link' different categories together, or rather a way to describe relationships between one category and another.
This is where functors come into play:
"Every sufficiently good analogy is yearning to become a functor."
- John Baez
A functor is a mapping between categories with the property, that any property from the domain category will be transfered into the codomain category.
One can also think about functors as a container for data with defined properties.
In our notation that looks as follows:
The Data
Let \(F:\mathcal{C}\rightarrow\mathcal{D}\), it follows
$$A\in\lVert\mathcal{C}\rVert\Rightarrow F(A)\in\lVert\mathcal{D}\rVert$$
"if \(A\) is an object in \(\mathcal{C}\), then \(F(A)\) is an object in \(\mathcal{D}\)"
for all objects in \(\mathcal{C}\) and
$$f\in Morph(\mathcal{C})\Rightarrow F(f)\in Morph(\mathcal{D})$$
"if \(f\) is a morphism in \(\mathcal{C}\), then \(F(f)\) is a morphism in \(\mathcal{D}\)"
for all morphisms in \(\mathcal{C}\).
The properties
The following properties apply to all data of the form \(F(A)\)
$$F(Id_A)=Id_{F(A)}$$
for all identity-morphisms in \(\mathcal{C}\).
Basically this property shall ensure the existance of all identities from the domain category inside the codomain category.
Let then \(f:A\rightarrow B\) and \(g:B\rightarrow C\) be morphisms in \(\mathcal{C}\) and \(\circ_{\mathcal{C}}\) be the composition in \(mathcal{C}\) as well as \(\circ_{\mathcal{D}}\) be the composition in \(\mathcal{D}\) it follows that
$$F(g\circ_{\mathcal{C}}f)=F(g)\circ_{\mathcal{D}}F(f)$$
So if two morphisms in the domain category of \(F\) are composed, it's the same as composing the morphisms mapped with \(F\) in the codomain category.
These two properties are usually referred to as functor-laws.
Commutating diagrams
In category theory morphisms and their compositions are usually pictured as commutating diagrams. These diagrams consisting of objects and arrows enable one to easily spot equivalencies between different compositions.
The commutating diagram for a functor \(F\) looks as follows
It can easily be seen, that
$$F\circ f\Leftrightarrow F(f)\circ F$$
must apply. For this, we only have to follow the arrow on the right and the one on the bottom (left side of the equation), or alternatively the top arrow followed by the one on the left (right side of the equation).
There is a rule that applies to all commutating diagrams:
If there are multiple paths from one object to another, the compositions of these morphisms must be identical.
Functors in practice
So how do these functors look in practice and which functors may we encounter unknowingly already?
Besides providing a constructor to 'wrap' a value in it, a functor in practice needs to provide a function that allows applying a function to the wrapped value. This function is usually called fmap or map. The only requirement to this function is that the functor laws from above are upheld.
It's type is the following
fmap :: Functor f => (a -> b) -> f a -> f b
So the function takes two parameters; a morphism from a to b, as well as a functor with a value of type a and returns a functor with a value of type b.
Some people may already recall a function that does just that and, yes, lists are functors at least in most modern programming languages. But at least for Kotlin they are not the only functors provided as a standard type. Any? and all its child types are also functors, In their case the map function is implemented with the elvis operator ?. though.
To check up on my claim regarding lists, let's look at them in detail:
- listOf(x) is the same as \(F(x)\) as it maps the object \(x\) from the category \(\mathcal{X}\) to the object \([x]\) from the category \(\mathcal{L}\).
- Let l=listOf(1,2,3), and fun f(x: Int) = x+1 it follows l.map(::f)==listOf(2,3,4). So map is equvalent to \(F(f)\) and maps a morphism \(f\) from the category \(\mathcal{X}\) to it's equivalent morphism in \(\mathcal{L}\).
- Let fun <A> A.id() = this, it follows listOf(1,2).id()==listOf(1.id(),2.id()).
- Let fun <A,B,C> compose(f: (A)->B, g: (B)->C): (A)->C = {input -> g(f(input))}, and let fun f(x: Int) = x+1 as well as fun g(x: Int) = x*3. It follows listOf(1,2).map(compose(f,g))==listOf(compose(f,g)(1),compose(f,g)(2))
With that all the requirements for a functor are satisfied and thus, lists are functors.
