13. Understanding Monads

Written by Massimo Carli

The monad is probably one of the most important concepts in functional programming, and it has the reputation of being very difficult to understand. This is probably true, but the amount of effort you need also depends on the approach you want to follow.

A possible approach is based on the formal definition: A monad is a monoid in the category of endofunctors. None of the concepts mentioned in this definition are new to you. In Chapter 2, “Function Fundamentals”, you learned the concept of categories. In Chapter 11, “Functors”, you learned everything you needed to know about functors. Finally, in Chapter 12, “Monoids & Semigroups”, you learned the concept of monoids. Unfortunately, this approach also requires some mathematical knowledge that’s outside of the scope of this book.

For this reason, in this book, you’ll look at monads in a pragmatic way. Here, you’ll start from the problem of the composition of functions in the Kleisli category and prove that monads are a beautiful way to do it.

In this chapter, you’ll have the opportunity to:

• Revise the concept of a category.

• Meet the Kleisli category again.

• Meet the fish operator, >=>, and the bind operator, >>=.

• Revise the concept of functor using the functor laws in the implementation of fish and bind.

• Implement fish for the List<T> typeclass.

• Understand why monads are so important.

• See some practical examples of monads for Optional<T> and List<T>.

You’ll learn all this by using some exercises.

The road to monads!

As mentioned in this chapter’s introduction, you already have all the skills you need to understand the concept of monads. You just need some guidance. You basically need to revise some of the concepts you’ve met in the previous chapters and use them to learn something new. In this section, you’ll follow a pragmatic approach to solving a simple problem. Given two functions:

• f of type (A) -> M<B>
• g of type (B) -> M<C>

You want to define a new function of type (A) -> M<C> that’s the composition of the two. What you represent with M<A> is a generic typeclass you usually get from A using a type constructor. Examples of M<A> are List<A> or Optional<A>.

Note: One way to abstract any possible typeclass M<A> is called higher kind. At the moment, Kotlin doesn’t provide this feature. But some frameworks — like Arrow, which you’ll learn in Chapter 19 — provide tools to generate something similar. Arrow, for instance, uses the @higherkind annotation to generate a class Kind<ForM, T> as an abstraction of M<T>. With this, Optional<A> would become Kind<ForOptional, A> where ForOptional is a placeholder representing the Optional<A> type. The Optional type also generated from this Kind. For right now, don’t worry about it. You’ll learn everything about this in Chapter 19, “Arrow”. The only thing you need to understand is that what you’ll create using M<A> or Kind<ForM, A> will be valid for any specific typeclass.

What you want to implement isn’t a classic composition between two functions because the output type for f is M<B>, but the input type for g is B. Solving this problem is precisely what will allow you to understand what a monad is.

It’s time to start from the concept of category.

Note: In this chapter, you’ll represent generic types like M<T>. Sometimes, you’ll represent the same type with M<A>, M<B> or using any other letter for the type parameter like M<X>. When defining a function, which letter you use doesn’t matter. As an example, this means you can define a lift like:

fun <T> lift(value: T): M<T> { ... }

Or like:

fun <A> lift(value: A): M<A> { ... }

The important thing is using different letters when it matters, like:

fun <A, B, C> Fun<A, B>.compose(g: Fun<B, C>): Fun<A, C> { ... }

In short, don’t be confused by the specific letter used.

What is a category?

As you’ve learned so far, a category is the model you use to study the theory of composition. A category is a bunch of objects and some arrows between them called morphisms that follow some fundamental properties:

1. Composition
2. Associativity
3. Identity

There are different types of categories, but the one that’s most important for you is the category of types and functions. For this category, the previous properties become:

1. For every pair of functions f of type (A) -> B, and g of type (B) -> C, there must be a function of type (A) -> C that’s the composition of f and g. You usually represent this function as g ◦ f, which you read as “g after f”, or as f compose g, where compose is a function you defined as:

typealias Fun<A, B> = (A) -> B

inline infix fun <A, B, C> Fun<A, B>.compose(
  crossinline g: Fun<B, C>
): Fun<A, C> = { a: A ->
  g(this(a))
}

2. For all functions f of type (A) -> B, g of type (B) -> C, and h of type (C) -> D, you can say that:

h ◦ (g ◦ f) = (h ◦ g) ◦ f

Or, in another way, that:

(f compose g) compose h = f compose (g compose h)

3. For every type A, there’s always a function of type (A) -> A. You call this identity and represent it as ia. It has the following property for every function f:

ia ◦ f = f ◦ ia = f

But why are functions and compositions so important? You already learned that it’s easier to understand programs if you decompose them into many small pieces, as you can implement and test them more easily. All these pieces are functions. To build your program, you need to put all the functions together using composition.

The properties of a category are definitions you need to remember and digest to really understand how particular functions compose themselves. Some functions are special and allow you to define fundamental categories. One of these is the Kleisli category.

The Kleisli category

In the category of types and functions, your objects are types like A, and the morphisms are functions of type (A) -> B. So far, so good.

In the previous chapters, you learned that you can start from a type A and create a new type you represent as M<A> using a type constructor. For instance, given a type A, you can define the type Optional<A> or the type List<A>. In the first example, you replaced M with Optional, and in the second, M with List. To get an M<A> from A, you defined the lift function. M is also the way you define a typeclass.

Note: From this point, you’ll use M<A> to define any new type you create from A using a type constructor. As mentioned earlier, to do so, you’d need a generic way to represent any M<A>. To ensure the code you’ll write compiles, use a simple workaround: You’ll represent M<A> as a typealias of some existing typeclass.

You define a category in terms of objects and morphisms. In a Kleisli category, objects are types. Some of these types are in the form of A, and others are in the form of M<A>. For instance, Int is a possible type, and Optional<String> is another. It’s the same for Int and List<String>. They all are types. In a Kleisli category, morphisms are functions of the type (A) -> M<B>. You’re basically considering functions between a type A and a possible embellishment or decoration of the type B you represent with M<B>.

Note: Spoiler alert: M<A> is also a functor, as you’ll see later.

An example of these functions have type (A) -> Optional<B>, (A) -> List<B> or the (A) -> Pair<B, String> you defined as Writer<A, B> in Chapter 3, “Functional Programming Concepts”.

typealias Writer<A, B> = (A) -> Pair<B, String>

The Writer<A, B> type is a perfect example because you implemented the composition using the following code:

infix fun <A, B, C> Writer<B, C>.after(
  w: Writer<A, B>
): Writer<A, C> = { a: A ->
  val (b, str) = w(a)
  val (c, str2) = this(b)
  c to "$str\n$str2\n"
}

Because Writer<A, B> is just a typealias of (A) -> Pair<B, String>, you might think of it as a special case of (A) -> M<B> where M<B> is Pair<B, String>.

Note: Second spoiler alert: Writer<A, B> with the after function is a monad!

Of course, this is the implementation of composition for the typeclass Writer<A, B>. Can you implement the same for all the functions of the Kleisli category? The answer is yes! To understand how, imagine this is possible using a special operator you call fish and represent as >=>. How can you implement the fish operator, >=>, then?

Note: Yes, you really call that operator “fish”! This is the name Bartosz Milewski gave it in his Category Theory course on YouTube. The reason is that it looks like a shark. You’ll give it a more formal name later.

The fish operator >=>

Suppose you want to define a composition between two functions in the Kleisli category. Given a function f of type (A) -> M<B> and a function g of type (B) -> M<C>, you want to define an operator, called the fish operator, which you represent as >=>. It does the following:

((A) -> M<B>) >=> ((B) -> M<C>) -> ((A) -> M<C>)

Or

f >=> g

The result of f >=> g is a function of type (A) -> M<C>. To better understand how to implement this operator, it’s crucial to note that the output type for f is M<B>, while the type for the input of g is B. There’s some type impedance because B isn’t M<B>. The goal is to define what you really need to create an implementation of the fish operator for all the typeclasses M.

What you need to get is a function of type (A) -> M<C>, which is a function from A to M<C>. Open Monad.kt in the material for this project and add the following code:

typealias M<T> = List<T> // 1

infix fun <A, B, C> Fun<A, M<B>>.fish( // 2
  g: Fun<B, M<C>> // 3
): (A) -> M<C> = // 4
  { a: A ->
    TODO("Add implementation")
  }

Here, you define:

1. M<T> as a typealias of List<T>, as mentioned earlier. This allows you to successfully compile all the code you’ll write.

2. fish as an infix extension function for the type Fun<A, M<B>>.

3. g as the parameter for fish of type Fun<B, M<C>>.

4. Fun<A, M<C>> as the return type of fish.

At the moment, you just know that you need to return a function of A, so you define it as a lambda with a single parameter a of type A. Because you have f, the first — and probably the only — thing you can do now is apply it to the input a of type A like this:

infix fun <A, B, C> Fun<A, M<B>>.fish(
  g: Fun<B, M<C>>
): (A) -> M<C> =
  { a: A ->
    val mb : M<B> = this(a) // HERE
    TODO("Add implementation")
  }

Here, mb has type M<B>, which you defined explicitly to make the code clearer.

Now, you have g, which has type (B) -> M<C>. The question is: How can you use mb of type M<B> and g of type (B) -> M<C> to get a value of type M<C>?

At this point, you don’t know it yet, but you can delegate this operation to another operator called bind, which you represent with >>=.

Note: Kotlin doesn’t allow you to define operators with the names >=> or >>=. This is why you’ll use the names fish and bind.

Represent the type of >>= with the following code you add in Monad.kt:

infix fun <B, C> M<B>.bind(
  g: Fun<B, M<C>>
): M<C> {
  TODO("Add implementation")
}

Here, you define bind as an extension function of M<B>, accepting g of type (B) -> M<C> as an input parameter, and returning a value of type M<C>. Assuming you have the implementation of bind for your typeclass M, fish becomes:

infix fun <A, B, C> Fun<A, M<B>>.fish(
  g: Fun<B, M<C>>
): (A) -> M<C> =
  { a: A ->
    val mb = this(a)
    mb.bind(g) // HERE
  }

Note: As you can easily verify, the previous code compiles as soon as you use M<A> as a typealias of List<A>. This is also true for any other type that — as you’ll see later — provides a map function or, in other words, is a functor.

At this point, it’s crucial to understand that:

• bind is somehow related to the typeclass M.
• If you define bind for M, you also define fish.

These two sentences are very powerful because they allow you to have a first pragmatic definition of monad.

A pragmatic definition of monad

A first pragmatic definition of monad comes from what you learned above. A monad is basically a typeclass M for which you define the following two functions:

• bind of type (M<A>, Fun<A, M<B>>) -> M<B>
• lift of type (A) -> M<A>

Given bind and lift, you can implement the fish operator and compose two functions in the related Kleisli category. This means that a possible way to define a monad is through a Monad<T> interface, like the following you add to Monad.kt:

interface Monad<T> {

  fun lift(value: T): Monad<T>

  fun <B> bind(g: Fun<T, M<B>>): Monad<B>
}

Implementing bind isn’t so obvious, but you can make the implementation easier as soon as you realize that M<T> is a functor!

What is a functor?

In Chapter 11, “Functors”, you learned that a functor is essentially a way to map objects and morphisms of a category C in objects and morphisms in a category D following some rules that you call functor laws.

You probably remember that a functor preserves structure, and you represent this with the following properties:

• Composition, which means that F (g ◦ f) = F g ◦ F f.
• Identity, which means that F ia = i Fa.

The first law says that a functor maps the morphism g ◦ f composition of f and g in the composition of the morphisms Fg and Ff.

The second law says that a functor maps the identity of the source category in the identity of the category you use as the destination.

The good news now is that the types you’re representing with M<A> are exactly the functor you called Fa before. If you think of the objects for the source category types A and the objects of the destination category as M<B>, you understand that a function of type (A) -> M<B> is exactly the functor that maps an object of the source category to the object of the destination category.

As you see in Figure 13.1, the composition of Ff and Fg is equal to F (g ◦ f). You can write this like:

Fg ◦ Ff = F (g ◦ f)

To make the concept more familiar, replace F with M and see that:

1. F is basically a way to map the object a of type A in C to the object of type Fa in D. If you replace F with M, you realize that this is exactly the function that allows you to map values of type A to values of type M<A>.
2. A function f of type (A) -> B in C is mapped to a function Ff of type (M<A>) -> M<B> in D.
3. Composing a function f of type (A) -> B with g of type (B) -> C in the category C is equivalent to composing the two functions of type (M<A>) -> M<B> and (M<B>) -> M<C> in D.
4. Finally, the functor laws say that composing f and g and then lifting to M is equivalent to lifting f and g using M and then composing.

In other words, given a value of type A, you can do the following:

1. Apply f to the value of type A and get a value of type B.
2. Apply g to the value of type B and get a value of type C.
3. Lift the result of type C into a value of type M<C>.

Another option is to:

1. Lift the value of type A into a value of type M<A>.
2. Invoke map on the value of type M<A>, passing the function f as a parameter and getting a value of type M<B>.
3. Invoke map on the value of type M<B>, passing g as a parameter and getting a value of type M<C>.

The functor laws say that the values of type M<C> you get in the two distinct ways are exactly the same.

Now, you’ll use these properties to simplify the implementation of the bind operator, >>=.

Monads as functors

You want to find an easier way to implement bind for all the M<B>. What the bind operator does is apply g to a value of type M<B>. Because M<B> is a functor and g is of type (B) -> M<C>, you can apply g to M<B>, invoking the map function. This is because a functor rule says that lift and map is equivalent to map and lift.

In other words, given a type A, you can first lift it to M<A> and then apply a function f of type (A) -> B using M<A>.map(f). Or you can first apply the function f to the value of type A and get a value of type B and then lift it, getting an M<B>.

Given that, you can rewrite bind in Monad.kt like this:

infix fun <B, C> M<B>.bind(
  g: Fun<B, M<C>>
): M<C> {
  val tmp : M<M<C>> = map(g) // HERE
  TODO("Fix the return type")
}

As defined explicitly, the type of the temporal variable tmp is M<M<C>>. What you get from map is a double embellishment. As you did earlier, you can think of a function, called flatten, that does exactly what its name states. It flattens the type M<M<A>> to a single M<A>. Now, add the following function to Monad.kt:

fun <A> M<M<A>>.flatten(): M<A> {
  TODO("")
}

And change bind like this:

infix fun <B, C> M<B>.bind(
  g: Fun<B, M<C>>
): M<C> =
  map(g).flatten() // HERE

Note: Here, you’re assuming that M<A> has the map function following the functor laws. If you’ve used M<A> as a typealias of List<A>, this comes for free.

With this, you can also simplify the implementation for fish like this:

infix fun <A, B, C> Fun<A, M<B>>.fish(
  g: Fun<B, M<C>>
): (A) -> M<C> =
  { a: A ->
    this(a).bind(g) // HERE
  }

What you need now is an implementation of flatten for your typeclass M. A practical example can help you understand how to do that.

A practical example of a monad

As an example of what you’ve found so far, you’ll now implement the fish operator for List<T>. All you have to do is define the implementation for listFlatten.

Note: As you’ve done before, you change the name of flatten in listFlatten to avoid conflict with the code you wrote above. You’ll do the same for other functions.

You basically need to define the following function in the ListMonad.kt file you find in the material for this chapter:

fun <T> List<List<T>>.listFlatten(): List<T> {
  TODO("")
}

This function starts from a List<List<T>> and must return a List<T>. One of the implementations to do that is the following, which you can add to the same ListMonad.kt:

fun <T> List<List<T>>.listFlatten(): List<T> =
  this.fold(mutableListOf()) { acc, item ->
    acc.apply {
      addAll(item)
    }
  }

You can also define listBind like this:

infix fun <B, C> List<B>.listBind(
  g: Fun<B, List<C>>
): List<C> =
  map(g).listFlatten()

Finally, the implementation for listFish is:

infix fun <A, B, C> Fun<A, List<B>>.listFish(
  g: Fun<B, List<C>>
): Fun<A, List<C>> = { a: A ->
  this(a).listBind(g)
}

As proof of this, you can add the following code to ListMonad.kt:

val countList: (Int) -> List<Int> =
  { n: Int -> List(n) { it + 1 } } // 1

val intToChars =
  { n: Int -> List(n) { 'a' + n } } // 2

fun main() {
  val fished = countList listFish intToChars // 3
  fished(3) pipe ::println
}

In this example, you define:

1. countList as a function of type (Int) -> List<Int> that returns a list containing values from 1 to an Int value you pass in as input. For instance, given 2, it returns the List<Int> with values 1 and 2.
2. intToChars as a function of type (Int) -> List<Char> that returns the List<Char> you get by adding the input value to a. For instance, passing 2, you get a List<Char> with two cs.
3. fished as a variable of type (Int) -> List<Char> containing the composition of countList and intToChars.

Run the previous code, and you get:

[b, c, c, d, d, d]

Of course, this is just an example, and it doesn’t really matter what the two functions you’re composing do. The important thing is that listFish works. But, what’s the logic of listFish?

In the previous section:

1. You saw that a monad is a functor, and it has a map.
2. You implemented flatten as a way to map values of type M<M<A>> in values of type M<A>.

The map and flatten names should remind you of a function called flatMap, which you met in Chapter 7, “Functional Data Structure”. This is the same function, and what you learned here is the reason for its name.

To prove it, just add the following code in main in ListMonad.kt:

fun main() {
  // ...
  countList(3).flatMap(intToChars) pipe ::println
}

Run the code now, and you get exactly the same result:

[b, c, c, d, d, d]

Exercise 13.1: How would you make the Optional<T> data type you created in Chapter 9, “Data Types”, a monad? If you need help, you can check out the solution in Appendix L.

Exercise 13.2: What’s the relation between the fish operator, >=>, and flatMap? Can you express the latter in terms of the former for Optional<T>? A solution is in Appendix L if you need it.

Why monads?

This is all fascinating, but why do you really need monads? The answer is in the problem monads solve and precisely in the composition of what you call Kleisli arrows and represent as a function of type (A) -> M<B>.

In Chapter 3, “Functional Programming Concepts”, you learned the difference between a pure and impure function. A pure function:

• Has body that’s referentially transparent.
• Doesn’t have any side effects.

You also learned that you can transform a function with side effects into a pure function by just making the effect part of the returning type. The Writer<A, B> type is a great example of this. In Exercises 13.1 and 13.2, you implemented flatMap for the Optional<T> type. It’s basically a method to compose functions of type (A) -> Optional<B>.

Note: From here, you’ll use a flatMap implementation for Optional<T> that’s the solution to Exercise 13.1. Feel free to solve the exercise first or go directly to the solution in Appendix L and copy its code in OptionalMonad.kt. If you solved the exercise, just use that code directly.

A partial function is a function that isn’t valid for all the values in its domain. A very simple example is the following, which you should write in OptionalMonad.kt:

fun strToInt(str: String): Int =
  str.toInt()

This is a very simple function that converts a String in an Int. Of course, not all the Strings contain a value that can be converted into Ints. Run:

fun main() {
  strToInt("123") pipe ::println
}

And you get:

123

Run the code:

fun main() {
  strToInt("onetwothree") pipe ::println
}

And you get:

Exception in thread "main" java.lang.NumberFormatException: For input string: "onetwothree"
	at java.lang.NumberFormatException.forInputString(NumberFormatException.java:65)

This is because "onetwothree" can’t be converted to Int. strToInt is an example of a partial function because it doesn’t make sense for all the values in its domain. More importantly, strToInt is not pure because it has side effects, which is the exception that it throws when the input isn’t valid. How can you make strToInt pure? You already know the answer. You make the effect part of the return type.

In Chapter 14, “Error Handling With Functional Programming”, you’ll see a better way to handle this case, but for now, you can just model the result using an Optional<Int> and replace the current strToInt implementation with the following:

fun strToInt(str: String): Optional<Int> = // 1
  try {
    Optional.lift(str.toInt()) // 2
  } catch (nfe: NumberFormatException) {
    None // 3
  }

In this code, you:

1. Replace the strToInt return type with Optional<Int>.
2. Convert the String value to Int and lift the result in the case of success.
3. Return None in the case of NumberFormatException.

Now, run the main again, and you get something like this:

com.raywenderlich.fp.exercise1.None@372f7a8d

Besides the fact that toString() isn’t implemented for None, you see that you get None as the result. A test for this would now be as easy as writing in the OptionalMonadKtTest.kt file in the material for this project:

class OptionalMonadKtTest {

  @Test
  fun `When input is not valid returns None`() {
    assertThat(strToInt("onetwothree")).isEqualTo(None)
  }
}

Once you have a pure strToInt, you might need to compose it with another function that also returns an Optional<T>. A possible example of a function you might need to compose with the previous is the following, which you can add to OptionalMonad.kt:

fun root(number: Int): Optional<Double> =
  if (number < 0) None else Optional.lift(sqrt(number.toDouble()))

This is another partial function that accepts only positive values.

Note: In this case, you’re ignoring imaginary numbers.

How can you then compose strToInt with root? The answer is simple now, and it’s one you accomplish with the following code:

fun main() {
  val strToRoot = ::strToInt optionalFish ::root // 1
  strToRoot("onetwothree") pipe ::println // 2
  strToRoot("123") pipe ::println // 3
}

Here, you:

1. Use optionalFish to get the function strToRoot, which is the composition of strToInt and root.
2. Invoke strToRoot with a value not in the domain.
3. Invoke strToRoot again with a valid input.

Running the previous code, you get something like:

com.raywenderlich.fp.exercise1.None@1f32e575
Some(value=11.090536506409418)

If you want to use the flatMap you implemented in Exercise 13.2, run the following code:

fun main() {
  // ...
  strToInt("onetwothree").flatMap(::root) pipe ::println
  strToInt("123").flatMap(::root) pipe ::println
}

Getting the same output:

com.raywenderlich.fp.exercise1.None@1f32e575
Some(value=11.090536506409418)

Monads are important because they allow you to compose functions that handle side effects as part of the return type.

Key points

• A monad is a monoid in the category of endofunctors.
• Monads solve the problem of the composition of Kleisli arrows, which are functions of type (A) -> M<B>.
• Kleisli arrows are how you model functions from a type A to an embellished version of a type B you represent as M<B>.
• The embellishment of a type M<A> is a way to encapsulate effects in the return type of a function.
• Monads are functors and provide a map function following the functor laws.
• You implement the fish operator, >=>, to achieve composition between two Kleisli arrows. It composes a function of type (A) -> M<B> with a function of type (B) -> M<C> to get a function of type (A) -> M<C>.
• The bind operator, >>=, is a way to solve the type impedance between a function returning a value of type M<B> and a function accepting a value of type B in input.
• The flatten function allows you to simplify the way you implement bind in the case of functors. It has type (M<M<A>>) -> M<A>.
• You can implement flatMap using fish, bind and flatten.
• Monads are the way you compose functions encapsulating side effects in the result type.

Where to go from here?

Congratulations! This is probably the most challenging chapter of the book but also the most rewarding. You now understand what a monad is, and you’ll see many different and important monads in the third section of the book. Now, it’s time to write some code and apply all the concepts you learned in the first two sections of the book.