Home Android & Kotlin Books Functional Programming in Kotlin by Tutorials

13
Understanding Monads Written by Massimo Carli

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled text.

You can unlock the rest of this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

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:

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

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

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

ia ◦ f = f ◦ ia = f

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.

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

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

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

f >=> g

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

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

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

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
  }

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:

interface Monad<T> {

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

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

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.

F N P z q m a G v V d G p C u c n ° d F y B ( m h ) °
Yodeco 97.1: Yiqtely uycevmn

Fg ◦ Ff = F (g ◦ f)

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.

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

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

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

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
  }

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.

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

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

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

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

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
}

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

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

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

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

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

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

123

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

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

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

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

class OptionalMonadKtTest {

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

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

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

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

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

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

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.

14. Error Handling With Functional Programming 12. Monoids & Semigroups

Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.

© 2022 Razeware LLC

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a raywenderlich.com Professional subscription.

Unlock Now

To highlight or take notes, you’ll need to own this book in a subscription or purchased by itself.

Read for Free with a Subscription

Buy this book for $59.99