11.
Functors
Written by Massimo Carli
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
In Chapter 9, “Data Types”, you met the map function for the first time. You learned that it’s one of the most important functions many data types provide and that it’s related to the concept of a functor. But what is a functor, and why is map so important? In this chapter, you’ll learn:
- What a functor is and how it’s related to category theory.
- How to apply the concept of a functor to the category of types and functions.
- What functor laws are and how to use equational reasoning to verify them.
- How to use the
FList<T>andList<T>functors. - What a bifunctor is in relation to category theory.
- How to implement
bimapfor algebraic data types.
This is a very theoretical chapter without exercises or challenges. However, it’s helpful for getting you into a more functional mindset.
What is a functor?
The definition of functor is quite simple. A functor is basically a way to map one category in another while preserving the structure. But what does structure of a category mean? The first step to understanding is a quick revision of the concept of category.
In Chapter 2, “Function Fundamentals”, you learned that a category is a bunch of objects and some arrows between them, which are called morphisms. A category has three fundamental properties:
- Composition
- Associativity
- Identity
In Figure 11.1, you see an example of a category with two objects and one morphism between them in addition to the identity morphisms that, by definition, must be present for all objects.
Note: Remember that in a category, every object must have a morphism, called identity. You represent this as an arrow from the object back to itself. This is always true, even though, for simplicity, you won’t see them in all the following pictures.
Categories tend to have structures because objects and morphisms give them a sort of pattern. For instance, you might have another category, like in Figure 11.2, that also has two objects and a morphism between them. Although they’re two distinct categories, you can recognize that they have the same structure or recall the same pattern.
This offers the chance to map a category into another one, keeping the same structure, which recalls the same pattern. In the previous example, the pattern has two objects and one morphism between them.
A functor, then, is something more than just mapping between two categories. It must also preserve the structure. This means a functor has to map objects into objects and morphisms into morphisms, following some rules.
Consider, then, two categories, C and D, as in Figure 11.3:
There you have:
- A category C with two objects, a and b.
- A category D with two objects, a’ and b’.
- A functor F mapping object a to a’ and object b to b’.
As you see in the image, you can represent a’ as Fa and b’ as Fb.
Now, category C might have some structure you can represent with a morphism f from a to b. The structure depends on the category, but in this example, you can think of f as a single morphism from a to b. If this is the case, a functor also has to map f into another morphism in the category D. This is where the concept of preserving the structure becomes fundamental. If category C has a morphism f from a to b, a functor must map it to another morphism, which you represent as Ff, between a’ and b’.
You can also say that the functor must map the morphism f to a morphism Ff from Fa to Fb.
Note: It’s important to say that you might map f into another morphism between two objects different from a’ and b’. That’s perfectly legal, but you wouldn’t define a functor in that case.
Of course, you might have many different morphisms between a and b. In category theory, the set of all the morphisms between two objects has a name: the hom-set.
With C(a, b), you can represent the hom-set of all the morphisms between a and b in the category C. At the same time, D(Fa, Fb) can represent the hom-set of all the morphisms between Fa and Fb. A functor, then, is a way to map each morphism in C(a, b) to a morphism in D(Fa, Fb). Because the hom-sets are sets, and you’re mapping elements of a set into elements of another set, a functor is a function.
A functor is an exceptional function, though, because mapping all the morphisms of the hom-set C(a, b) to morphisms in the hom-set D(Fa, Fb) isn’t enough. A functor must also preserve — guess what — composition! Consider, then, Figure 11.5:
This figure has several important things to note:
- The category C has three different objects: a, b and c, with a morphism f from a to b and a morphism g from b to c.
- If C is a category, because of the composition property, another morphism must exist from a to c: the composition of the morphisms f and g. You represent it as g ◦ f and read it as “g after f”.
- From the definition of a functor, you know that it maps a to a’ = Fa, b to b’ = Fb and c to c’ = Fc in the category D.
- The functor also maps the morphism f to Ff and the morphism g to Fg.
- Because D is a category, there must be a morphism from Fa to Fc that’s the composition of the morphisms Ff and Fg. You represent this as Fg ◦ Ff and read it as “Fg after Ff”.
What makes F a functor is that F (g ◦ f) = Fg ◦ Ff. In other words, the functor of the composition is the composition of a functor. This is the formal definition of the preservation of structure concept.
It’s crucial to note that:
- Not all mappings between objects and morphisms work like this. On the contrary, most don’t.
- What’s true for a morphism f from a to b must be true for the entire hom-set of all the morphisms from a to b.
- In the case of identity, it must be true that F ia = i Fa. This means that a functor must map identity morphisms ia for every object a to the identity for the object Fa, which you can represent as i Fa.
The points above are the rules a functor must follow, usually referred to as the functor laws. In short, a functor must preserve:
- Composition, which means that F (g ◦ f) = Fg ◦ Ff.
- Identity, which means that F ia = i Fa.
This is true for all the categories. But you, as an engineer, are interested in one particular category: the category of types and functions.
Note: To better understand these concepts, take your time reviewing this section as many times as you need. Try to imagine categories with different structures and how the functor would change in each case.
Functors in programming
In the previous section, you learned what a functor is in terms of category theory. But, as a programmer, you’re particularly interested in one category: the one where objects are types and morphisms are functions. In this case, you’re working with endo-functors. The “endo” prefix means “internal” and emphasizes that the functor maps types in types and functions in functions.
sealed class Optional<out T> {
companion object {
@JvmStatic
fun <T> lift(value: T): Optional<T> = Some(value)
@JvmStatic
fun <T> empty(): Optional<T> = None
}
}
object None : Optional<Nothing>()
data class Some<T>(val value: T) : Optional<T>()
fun <A, B> Optional<A>.map(fn: Fun<A, B>): Optional<B> =
when (this) {
is None -> Optional.empty()
is Some<A> -> Optional.lift(fn(value))
}
((A) -> B)) -> ((Optional<A>) -> Optional<B>)
Functor laws
In the previous section, you proved that the map function you implemented in Chapter 9, “Data Types”, maps functions of type Fun<A, B> into functions of type Fun<Optional<A>, Optional<B>>. Previously, you learned how to create an Optional<A> from A using a type constructor or a function like lift. Unfortunately, this isn’t enough to prove that, with the map function, Optional<T> is now a functor.
Preserving identity for Optional<T>
To prove that the Optional<T> data type and map function you implemented above are a functor, you need to prove some laws. The first is about identity. You basically need to prove the following equation:
F ia = i Fa
fun <A> id(a: A): A = a
sealed class Optional<out T> {
companion object {
@JvmStatic
fun <T> lift(value: T): Optional<T> = Some(value)
@JvmStatic
fun <T> empty(): Optional<T> = None
}
}
object None : Optional<Nothing>()
data class Some<T>(val value: T) : Optional<T>()
fun <A, B> Optional<A>.map(fn: Fun<A, B>): Optional<B> =
when (this) {
is None -> Optional.empty()
is Some<A> -> Optional.lift(fn(value))
}
fun <A, B> Optional<A>.map(): Optional<A> = Optional.empty()
fun <A, A> Optional<A>.map(): Optional<A> = Optional.lift(id(value))
fun <A, A> Optional<A>.map(): Optional<A> = Optional.lift(value)
fun <A, A> Optional<A>.map(): Optional<A> = Some(value)
Preserving composition for Optional<T>
To prove that Optional<T> with the map function you implemented is a functor, you also need to prove that it preserves composition, which means that:
F (g ◦ f) = Fg ◦ Ff
fun <A, B> Optional<A>.map(): Optional<B> = Optional.empty()
fun <A, B> Some<A>.map(fn: Fun<A, B>): Some<B> = Some(fn(value))
g ◦ f = g ◦ f
The FList<T> and List<T> functors
In Chapter 9, “Data Types”, you implemented map for the FList<T> data type and used the map implementation Kotlin provides for the List<T> type. In this chapter, you won’t prove that FList<T> and List<T> are functors, but you’ll see an interesting property of the fact that they are. This is a consequence of the functor laws you previously proved for Optional<T>.
F ( g ◦ f ) = Fg ◦ Ff
val list = FList.of(1, 2, 3, 4, 5, 6, 7, 8, 9, 10) // 1
val left = list.map(f).map(g) // 2
val right = list.map(g after f) // 3
Bifunctors
In the previous sections, you learned what a functor is in terms of category theory, and you proved the functor laws for the Optional<T> data type. You also saw that knowing FList<T> and List<T> are functors helps you structure your code in an easier — and, probably more performant — way. Optional<T>, FList<T> and List<T> all have a single type parameter. In Chapter 9, “Data Types”, you also implemented Either<A, B> as an example of a data type with multiple type parameters. So, what’s the relationship between the concept of a functor and Either<A, B>?
fun <A, B, C, D> Either<A, B>.bimap(
fl: Fun<A, C>,
fr: Fun<B, D>
): Either<C, D> = when (this) {
is Left<A> -> Either.left(fl(left))
is Right<B> -> Either.right(fr(right))
}
fun <A, B, C, D> Pair<A, B>.bimap(
fl: Fun<A, C>,
fr: Fun<B, D>
): Pair<C, D> = fl(first) to fr(second)
Typeclasses
In the last three chapters, you learned how to implement some of the most important data types and saw how to make them work as functors. When you say that List<T> is a functor, you know that you can use a map function accepting another function as a parameter, and the functor laws will be valid. If you have multiple type parameters, you can say the same things about bifunctors and the bimap function.
Key points
- A functor is a way to map one category to another while preserving their structures.
- You define the structure of a category using objects and morphisms.
- A functor maps objects to objects and morphisms to morphisms.
- A type constructor is the mechanism a language provides to define a new data type using generics.
- Preserving structure means to preserve identity and composition.
- The functor laws are a formal definition of what it means to preserve identity and composition.
- You can define the category C×D as a Cartesian product of existing categories C and D. C×D has as objects all the pairs (c, d) you can create using all the c from C and d from D.
- You define morphisms in C×D depending on the specific type constructor.
- A functor mapping objects and morphisms from the category C×D is called a bifunctor.
- Bifunctors define the
bimapfunction. - A typeclass is the concept you use to represent common behaviors across different data types.
Where to go from here?
Congratulations! In this chapter, you learned more about functors, providing a solid base to the code you implemented in Chapter 9, “Data Types”. At the end of the chapter, you also met the concept of a typeclass. A functor is a typeclass. In the next chapter, you’ll see a couple of very important typeclasses: monoids and semigroups.