Functor

Programmers are familiar with the concept of functor and can recognize generic types such as lists as functors in object-oriented languages because they usually have a map/fmap/select method that transforms a list of type List<int> in a list List<string> through a function $f : int \rightarrow string$.

The truth is that the concept of functor in mathematics and the one in programming represent the same concept from different perspectives, the correspondence is not intuitive and obvious and we will show why.

Definition: Functor

A functor $F$ from a category $C$ to another $D$, denoted $F : C \rightarrow D$ is a mapping that sends $\forall x \in Ob(C)$ in an object $F(x) \in Ob(D)$ and which sends $\forall f \in Hom(C)$ to a morphism $F(f) \in Hom(D)$ such that:

• $F$ preserves the composition: $F(h \circ g)$ = $F(h) \circ F(g)$
• $F$ preserves the identity: $F(id_{x})$ = $id_{F(x)}$

Basically, a functor is a homomorphism (mapping that preserves the structure) between two categories.

Connection with programming

Returning to the correspondence between programming and mathematics, we can highlight the connection by considering the following example. Let's assume that within a program we have three types of data, int, bool and string with the following functions between them: $toString : int \rightarrow string$ and $isOdd : int \rightarrow bool$. Let's assume that our basic types represent a category with types being objects and functions being morphisms. If we introduce a functor called $List$ as a generic type that has a function $map : List\ a \rightarrow (a \rightarrow b) \rightarrow List\ b$ then the tuple $(List, map)$ represents the functor according to the definition given as the two mappings on objects and morphisms respectively.

note

This is just an example to conceptually illustrate the idea of a functor for a programmer, in reality the formalization of type systems in the form of categories is much more complex.

What we can see here is that the functor does not preserve an internal structure of a data type, this is irrelevant in a functional context, but it preserves the structure of relationships between data types. Also, for other generic types with different properties, several objects and morphisms must be included in the destination category for the functor. The destination category can include other objects and morphisms that are not mapped to from the source category.

Composition

Just as morphisms and functors can be composed, if we have functors $F : C \rightarrow D$ and $G : D \rightarrow E$, then there will exist a functor $G \circ F : C \rightarrow E$ that, when applied to $x \in Ob(C)$ and $f \in Hom(C)$, maps to $G(F(x)) \in Ob(E)$ and $G(F(f)) \in Hom(E)$, respectively.

Identity Functor

A special case of an (endo)functor is the identity functor $Id_C : C \rightarrow C$ (endofunctors are functors with the same source and destination category) which satisfies the properties:

$$Id_C(x) = x,\ \forall x \in Ob(C)$$ $$Id_C(f) = f,\ \forall f \in Hom(C)$$

Thus, this functor satisfies the relations for the composition of any functors $F : X \rightarrow C$, $G : C \rightarrow X$:

$$Id_C \circ F = F$$ $$G \circ Id_C = G$$

Resources

• ncatlab