11. Functors

Written by Massimo Carli

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> and List<T> functors.
• What a bifunctor is in relation to category theory.
• How to implement bimap for 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.

Note: Even if the functors in programming are endo-functors, you usually ignore the prefix and just call them functors.

Note: In this chapter, you’ll use different letters as type parameters. Sometimes you’ll use T and other types A and B. The name you use isn’t important, but in general, you’ll use T when referring to the generic data type and A and B when dealing with functions of type Fun<A, B>.

In your context, then, a functor maps types to types. It’s crucial to note that this must work for any type in the category. To represent a functor, you need a way to declare the type as a parameter and replace that parameter with the specific type you need. The good news is that you already know how to do this using generic types and type parameters. If F is your functor, you’ll represent it as F<A> where A is the type parameter. You often call F<A> a type constructor because you create a type, F<A>, starting from the type A.

But a functor doesn’t map just objects — it also must map functions. How can it do that? The best way to understand this is with an example. Open Optional.kt in this chapter’s material, and look at the code you implemented in Chapter 9, “Data Types”:

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>()

The Optional<T> data type provides the context of some object that can be present or not. To make things clearer, the Optional here is the F you’ve used so far to represent a functor, and Optional<T> is its type constructor, F<T>. When you replace the type parameter, you can have Optional<Int>, Optional<Boolean>, Optional<User>, etc. What you’ll define for Optional<T> will be valid whatever T’s specific type is.

Note: As you learned in Chapter 9, “Data Types”, you can use functions like lift to create an Optional<T> from an object of type T or, in general, an F<T> from a T.

Now, look at Figure 11.4 and assign a specific meaning to every object and morphism. In the source category, you have two types, A and B, and a function f from A to B of type Fun<A, B>. You know how to map the type A to Optional<A> and the type B to Optional<B>. To make Optional<T> a function, you need a way to map the function f of type Fun<A, B> to a function from Optional<A> to Optional<B> of type Fun<Optional<A>, Optional<B>>. This is precisely the map function you implemented in Chapter 9, “Data Types”, like this:

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))
  }

Note how the type of map is Fun<Fun<A, B> -> Fun<Optional<A>, Optional<B>>> because it:

• Receives as input a function of type Fun<A, B>.
• Returns an output of a function of type Fun<Optional<A>, Optional<B>>.

Another way to represent the type of map is:

((A) -> B)) -> ((Optional<A>) -> Optional<B>)

The function map above has the right type, but how can you be sure the Optional<T> with the previous map is actually a functor? You need to prove the functor laws.

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.

To prove that Optional<T> is a functor, you need to prove the functor laws, and specifically, that it preserves composition and identity.

To prove that your Optional<T> with the map you implemented is a functor, you need to prove that:

• F ia = i Fa
• F (g ◦ f) = Fg ◦ Ff

Proving these for the Optional<T> data type is a useful exercise. To do so, you use a technique called equational reasoning. Equational reasoning works here because Kotlin allows you to define pure functions as equalities. The left side is equal to the right side, and you can use the substitution model — as you learned in Chapter 3, “Functional Programming Concepts” — to replace the invocation of the function with the expression itself. Replacing the function invocation with the expression it represents is a technique called inlining. Of course, equality is symmetric, so you can also replace an expression with the invocation to the related function. In this case, you use a technique called refactoring.

Note: Not all programming languages provide tools to easily prove the functor laws. Sometimes, other programming languages provide unit tests to prove the same properties more empirically.

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

In other terms, given the identity function:

fun <A> id(a: A): A = a

You need to prove that by invoking map on an Optional<T> passing the id function, you get the identity for Optional<T>. Suppose, then, you have an Optional<T> you defined in this way, shown here again for convenience:

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>()

This definition says that an Optional<A> can be None or a Some<T>. You also defined map like this:

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))
  }

What you need to do is replace the function fn with an identity and see if you get the identity for Optional<T>. That would then be a function that returns exactly the same Optional<T> you pass as an input parameter.

If the Optional<T> is None, and the function fn is id, the map function becomes:

fun <A, B> Optional<A>.map(): Optional<A> = Optional.empty()

If the Optional<T> is Some<T>, and the function is id, you get:

fun <A, A> Optional<A>.map(): Optional<A> = Optional.lift(id(value))

Note that because id is the identity function, you can replace the type B with A. Given that id(value) = value, you get:

fun <A, A> Optional<A>.map(): Optional<A> = Optional.lift(value)

Or:

fun <A, A> Optional<A>.map(): Optional<A> = Some(value)

To summarize what you’ve just done, you’ll get:

• None if the Optional<T> is None.
• Some<T> if the Optional<T> is Some<T>.

This is the identity function for Optional<T>!

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

In this case, you also have two possible cases. If your Optional<T> is None, the map function becomes:

fun <A, B> Optional<A>.map(): Optional<B> = Optional.empty()

This means that if you have None, whatever function you apply, you always get None. This is true if you apply just f, g or the composition of the two. In the case of None, the left and right members are then the same.

In case of Some<T>, the map function becomes:

fun <A, B> Some<A>.map(fn: Fun<A, B>): Some<B> = Some(fn(value))

This means that you basically lose the option for the case when the value isn’t present. You remove the effect of the context, which consists in removing the F from the equation, getting:

g ◦ f = g ◦ f

This is true by definition, so you can conclude that the Optional<T> and map function you created defines a functor.

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

As you know, if you have two functions, f and g, and any functor F, the following equivalence is true:

F ( g ◦ f ) = Fg ◦ Ff

In the case of FList<T> and List<T>, you can write this as:

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

In this code, you:

1. Create an FList<Int>, but it could also be a List<Int>.
2. Invoke map a first time, passing the function f as a parameter and then a second time passing g as a parameter. This is the code version of the left side of the previous equation.
3. Invoke map, passing the composition of f and g as a parameter.

The functor laws say that the two sides of the equation are the same. The good news is in terms of performance. If N is the length of the list, the left side has complexity O(2N) while the right side has complexity O(N). In terms of complexity, a constant doesn’t matter: The composition g ◦ f takes approximately the same time as invoking f first and then g. In this case, you still have a single iteration, and the equivalent provides you the opportunity to write more readable code.

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>?

To understand this, start from the two categories in Figure 11.6:

Here, you have the categories:

• C, with the objects a and b and a morphism f between them.
• D, with the objects c and d and a morphism g between them.

So far, so good. Now, consider what’s in Figure 11.7:

In this figure, you have:

• The category C×D, which is the Cartesian product of the category C and D. This means each object in the category C×D is a couple of objects, (c, d), where c is an object of C, and d is an object of D.
• The morphism f from a to b in C and the morphism g from c to d in D becomes the morphism (f, g). Note how you go from the object (a, b) to (c, d) using both the functions, (f, g).
• Of course, C×D is a category, and you can create a functor F to another category E in the same way you did previously.

The main difference is that now the type constructor contains two different type parameters, not just one, which is why it’s called a bifunctor.

The relationship between bifunctors and algebraic data types you learned in Chapter 10, “Algebraic Data Types”, is intriguing. As you know, the type Pair<A, B> is an example of the product of types, while Either<A, B> is an example of the sum. In both cases, you can define a function, bimap, like the following one you already implemented in Either.kt in this chapter’s material:

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))
}

Depending on if Either<A, B> is a Left<A> or a Right<B>, you apply the function fl or fr, respectively. You never apply both. In the case of Pair<A, B>, you’d implement the same function in a similar way. Open Pair.kt, and write the following code:

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)

As you see, you define:

• bimap as an extension function of the Pair<A, B> type, receiving two functions as input parameters.
• fl as the first input parameter of type Fun<A, C> and fr as the second input parameter of type Fun<B, D>.
• Pair<C, D> as the return type for bimap.

It’s essential that you always invoke both fl and fr on the first and second properties, respectively, getting the object of type Pair<C, D> in return.

You won’t prove it in this book, but the good news is that you can define a functor or bifunctor for any algebraic data type.

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.

It also means that many data types have some common behavior. You usually refer to this common behavior with the concept of a typeclass. A functor is then a typeclass. In the following chapters, you’ll learn about other typeclasses like monoids, semigroups, monads and so on.

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 bimap function.
• 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.