From Functional Programming in Kotlin by Marco Vermeulen, Rúnar Bjarnason, and Paul Chiusano This article covers how monads, monad combinators, and functors work and why you shouldn’t be afraid of them.

Take 40% off Functional Programming in Kotlin by entering fccvermeulen into the discount code box at checkout at manning.com.

Many of us break out in a cold sweat on hearing the term monad. We have visions of others sitting in lofty ivory towers, completely disconnected from the reality that they live in while looking down on the rest of us. We hear them mumbling away about academic concepts that have little or no bearing on the real world.

Even though many have used the term monad in such a way in the past, we hope to show that this can be no further from the truth. The monad concept is highly practical in its application, and can truly transform the way we write code. Granted, this term (along with its relative the functor, which we will also come to know in this article) does find its origins in the academic roots of category theory. Despite this, we will learn that it’s highly practical and nothing to fear.

This chapter serves to demystify the ominous monad, and by the end of it you should have a working understanding of what it is, as well as how to apply it in a pragmatic way to your daily programming challenges.

Functors

The importance of laws and their relation to the functor

Whenever we create an abstraction like `Functor`, we should not only consider what abstract methods it should have, but also the laws we expect it to hold for the implementations. The laws you stipulate for an abstraction are entirely up to you, although Kotlin won’t enforce any of these laws on your behalf. If you are going to borrow the name of some existing mathematical abstraction like functor or monoid, we recommend using the laws already specified by mathematics. Laws are important for two reasons:

• Laws help an interface form a new semantic level whose algebra may be reasoned about independently of the instances. For example, when we take the product of a `Monoid<A>` and a `Monoid<B>` to form a `Monoid<Pair<A,B>>`, the monoid laws let us conclude that the “fused” monoid operation is also associative. We don’t need to know anything about `A` and `B` to conclude this.
• On a concrete level, we often rely on laws when writing various combinators derived from the functions of some abstract interface like `Functor`.

For `Functor`, we’ll stipulate the familiar law related to the `Par` data type. This laws stipulated that relation between the `map` combinator and an identity function as follows:

Listing 1. The functor law showing the relation between `map` and identity function

```
map(x) { a -> a } == x

```

In other words, mapping over a structure `x` with the identity function should itself be an identity. This law seems quite natural, and as we progressed beyond `Par`, we noticed that this law was satisfied by the `map` functions of other types like `Gen` and `Parser` too. This law captures the requirement that `map(x)` “preserves the structure” of `x`. Implementations satisfying this law are restricted from doing strange things like throwing exceptions, removing the first element of a `List`, converting a `Some` to `None`, and so on. Only the elements of the structure are modified by `map`; the shape or structure itself is left intact. Note that this law holds for `List`, `Option`, `Par`, `Gen`, and most other data types that define `map`!

To give a concrete example of this preservation of structure, we can consider `distribute` and `codistribute`, defined earlier. Here are their signatures again for reference:

```
fun <A, B> distribute(fab: Kind<F, Pair<A, B>>): Pair<Kind<F, A>, Kind<F, B>>

fun <A, B> codistribute(e: Either<Kind<F, A>, Kind<F, B>>): Kind<F, Either<A, B>>

```

Since we know nothing about `F` other than that it is a functor, the law assures us that the returned values will have the same shape as the arguments. If the input to `distribute` is a list of pairs, the returned pair of lists will be of the same length as the input, and corresponding elements will appear in the same order. This kind of algebraic reasoning can potentially save us a lot of work, since reliance on this law means we don’t have to write separate tests for these properties.

Monads: generalizing the `flatMap` and `unit` functions

Now that we understand a bit more about `Functor` and how to apply it, we discover that like `Monoid`, the `Functor` is just one of many abstractions that can be factored out of our libraries. But `Functor` isn’t the most compelling abstraction, as there aren’t that many useful operations that can be defined purely in terms of `map`.

Instead, let’s focus our attention on the more interesting interface called `Monad` that adds to the functionality of `Functor`. Using this interface, we can implement far more operations than with the functor alone, all while factoring out what would otherwise be duplicate code. It also comes with laws that allow us to reason about how our libraries behave in the way that we expect them to.

Recall that for several of the data types in this book, we have implemented `map2` to “lift” a function taking two parameters. For `Gen`, `Parser`, and `Option`, the `map2` function could be implemented as follows.

Listing 2. Implementations of `map2` for `Gen`, `Parser` and `Option`

```
fun <A, B, C> map2(
fa: Gen<A>,
fb: Gen<B>,
f: (A, B) -> C
): Gen<C> =                                              ❶
flatMap(fa) { a -> map(fb) { b -> f(a, b) } }

fun <A, B, C> map2(
fa: Parser<A>,
fb: Parser<B>,
f: (A, B) -> C
): Parser<C> =                                           ❷
flatMap(fa) { a -> map(fb) { b -> f(a, b) } }

fun <A, B, C> map2(
fa: Option<A>,
fb: Option<B>,
f: (A, B) -> C
): Option<C> =                                           ❸
flatMap(fa) { a -> map(fb) { b -> f(a, b) } }

```

Make a generator of a random `C` that runs random generators `fa` and `fb`, combining their results with the function `f`.

Make a parser that produces `C` by combining the results of parsers `fa` and `fb` with the function `f`.

Combines two `Options` with the function `f` if both have a value, otherwise returns `None`.

These functions have more in common than just the name. In spite of operating on data types that seemingly have nothing to do with one another, the implementations are identical! The only thing that differs is the particular data type being operated on. This confirms what we’ve been hinting at all along—that these are particular instances of some more general pattern. We should be able to exploit such a pattern to avoid repeating ourselves. For example, we should be able to write `map2` only once in such a way that it can be reused for all of these data types.

We’ve made the code duplication particularly obvious here by choosing uniform names for our functions and parameters, taking the arguments in the same order, and so on. It may be bit more difficult to spot in your everyday work. But the more libraries you write, the better you’ll get at identifying patterns that you can factor out into common abstractions.

Monads are everywhere! In fact, this is what unites `Parser`, `Gen`, `Par`, `Option`, and many of the other data types we’ve looked at so far. Much like we did with `Foldable` and `Functor`, we can come up with a Kotlin interface for `Monad` that defines `map2` and numerous other functions once and for all, rather than having to duplicate their definitions for every concrete data type.

In part 2 of this book, we concerned ourselves with individual data types, finding a minimal set of primitive operations from which we could derive a large number of useful combinators. We’ll do the same kind of thing here to refine an abstract interface to a small set of primitives.

Let’s start by introducing a new interface, call it `Mon` for now. Since we know that we eventually want to define `map2`, let’s go ahead and define it as in listing 3.

Listing 3. Defining a `Mon` interface as home for `map2`

```
interface Mon<F> {                                       ❶

fun <A, B, C> map2(
fa: Kind<F, A>,                                  ❷
fb: Kind<F, B>,                                  ❸
f: (A, B) -> C
): Kind<F, C> =
flatMap(fa) { a -> map(fb) { b -> f(a, b) } }
}

```

The `Mon` interface is parameterized with higher-kinded type of `F`

Use `Kind<F, A>` to represent `F<A>`

Will not compile since `map` and `flatMap` are not defined in context of F

In this sample, we’ve just taken the implementation of `map2` and changed `Parser`, `Gen`, and `Option` to the polymorphic `F` of the `Mon<F>` interface in the signature. We refer to in-place references to the kind of `F` using the `Kind` interface. But in this polymorphic context, the implementation won’t compile! We don’t know anything about `F` here, so we certainly don’t know how to `flatMap` or `map` over an `Kind<F, A>`!

What we can do is simply add `map` and `flatMap` to the `Mon` interface and keep them abstract. In doing so, we keep `map2` consistent with what we had before.

Listing 4. Introducing `flatMap` and `map` declarations to the `Mon` interface

```
fun <A, B> map(fa: Kind<F, A>, f: (A) -> B): Kind<F, B>

fun <A, B> flatMap(fa: Kind<F, A>, f: (A) -> Kind<F, B>): Kind<F, B>

```

This translation was rather mechanical. We just inspected the implementation of `map2`, and added all the functions it called, `map` and `flatMap`, as suitably abstract methods on our interface. This interface will now compile, but before we declare victory and move on to defining instances of `Mon<List>`, `Mon<Parser>`, `Mon<Option>` and so on, let’s see if we can refine our set of primitives. Our current set of primitives is `map` and `flatMap`, from which we can derive `map2`. Is `flatMap` and `map` a minimal set of primitives? Well, the data types that implemented `map2` all had a `unit`, and we know that `map` can be implemented in terms of `flatMap` and `unit`. For example, on `Gen`:

```
fun <A, B> map(fa: Gen<A>, f: (A) -> B): Gen<B> =
flatMap(fa) { a -> unit(f(a)) }

```

So let’s pick `flatMap` and `unit` as our minimal set of primitives. We’ll unify all data types under a single concept that have these functions defined. The interface shall be called `Monad`, and has abstract declarations of `flatMap` and `unit`, while providing default implementations for `map` and `map2` in terms of our abstract primitives.

Listing 5. Declaration of the `Monad` with primitives defined for `flatMap` and `unit`.

```
interface Monad<F> : Functor<F> {                                             ❶

fun <A> unit(a: A): Kind<F, A>

fun <A, B> flatMap(fa: Kind<F, A>, f: (A) -> Kind<F, B>): Kind<F, B>

override fun <A, B> map(
fa: Kind<F, A>,                                                       ❷
f: (A) -> B
): Kind<F, B> =
flatMap(fa) { a -> unit(f(a)) }

fun <A, B, C> map2(
fa: Kind<F, A>,
fb: Kind<F, B>,
f: (A, B) -> C
): Kind<F, C> =
flatMap(fa) { a -> map(fb) { b -> f(a, b) } }
}

```

`Monad` provides a default implementation of `map` and can so implement `Functor`

The override of `map` in `Functor` needs to be made explicit for successful compilation

We could have called `Monad` anything at all, like `FlatMappable`, `Unicorn`, or `Bicycle`. But monad is already a perfectly good name in common use. The name comes from category theory, a branch of mathematics that has inspired a lot of functional programming concepts. The name monad is intentionally similar to monoid, and the two concepts are related in a deep way.

To tie this back to a concrete data type, we can implement the `Monad` instance for `Gen`.

Listing 6. Declaring a `Monad` instance for `Gen` using concrete types

```

override fun <A> unit(a: A): GenOf<A> = Gen.unit(a)  ❷

override fun <A, B> flatMap(
fa: GenOf<A>,
f: (A) -> GenOf<B>
): GenOf<B> =
fa.fix().flatMap { a: A -> f(a).fix() }          ❸
}
}

```

The type `ForGen` is a surrogate type we provide to get around Kotlin’s limitations in expressing higher-kinded types

The type alias `GenOf<A>` is syntactic sugar for `Kind<ForGen, A>`

Down-cast all `GenOf<A>` to `Gen<A>` using provided extension method `fix()` for compatibility with `Gen.flatMap`

We only need to implement `flatMap` and `unit`, and we get `map` and `map2` at no additional cost. This is because `Monad` inherits these two functions from `Functor`. We’ve implemented them once and for all, and this for any data type which allows an instance of `Monad` to be created! But we’re just getting started. There are many more such functions that we can implement in this manner.

Now, write monad instances for `Par`, `Option` and `List`. Additionally, provide monad instances for `arrow.core.ListK` and `arrow.core.SequenceK`. The `ListK` and `SequenceK` types provided by Arrow are wrapper classes that turn their platform equivalents, `List` and `Sequence`, into fully equipped type constructors.

```

}

```

`State` looks like it could be a monad too, but it takes two type arguments, namely `S` and `A`. You need a type constructor of only one argument to implement `Monad`. Try to implement a `State` monad, see what issues you run into, and think about if or how you can solve this. We’ll discuss the solution later in this chapter.

```
data class State<S, out A>(val run: (S) -> Pair<A, S>) : StateOf<S, A>

```

We have already come to a point where we’ve defined primitives for the monad. Equipped with these, we can now move ahead and discover additional combinators. In fact, now we can look back at previous chapters and see if there were some other functions that we implemented for each of our monadic data types. Many of these types can be implemented as once-for-all monads, so let’s do that now.

The `sequence` and `traverse` combinators might be pretty familiar to you by now, and your implementations of them are probably all very similar. Implement them once and for all on `Monad<F>`.

```
fun <A> sequence(lfa: List<Kind<F, A>>): Kind<F, List<A>> = TODO()

fun <A, B> traverse(
la: List<A>,
f: (A) -> Kind<F, B>
): Kind<F, List<B>> = TODO()

```

One combinator we saw for `Gen` and `Parser` was `listOfN`, which allowed us to replicate a generator or parser `n` times to get a parser or generator of lists of that length. We can implement this combinator for all monads `F` by adding it to our `Monad` interface. We could also give it a more generic name such as `replicateM`, meaning “replicate in a monad”.

There was also a combinator for our `Parser` data type called `product`, which took two parsers and turned them into a parser of pairs. We implemented this `product` combinator in terms of `map2`. We can also write it generically for any monad `F`:

Implement `replicateM` to generate a `Kind<F, List<A>>`, with the list being of length `n`.

```
fun <A> replicateM(n: Int, ma: Kind<F, A>): Kind<F, List<A>> = TODO()

fun <A> _replicateM(n: Int, ma: Kind<F, A>): Kind<F, List<A>> = TODO()

```

Now think about how `replicateM` will behave for various choices of `F`. For example, how does it behave in the `List` monad? And what about `Option`? How would you describe the general meaning of `replicateM`?

There was also a combinator for our `Parser` data type called `product`, which took two parsers and turned them into a parser of pairs. We implemented this `product` combinator in terms of `map2`. We can also write it generically for any monad `F`:

Listing 7. Generic implementation of `product` using the `map2` combinator.

```
fun <A, B> product(
ma: Kind<F, A>,
mb: Kind<F, B>
): Kind<F, Pair<A, B>> =
map2(ma, mb) { a, b -> Pair(a, b) }

```

Here’s an example of a function we haven’t seen before. Implement the function `filterM`. It’s a bit like `filter`, except that instead of a function from `(A) -> Boolean`, we have an `(A) -> Kind<F, Boolean>`. Replacing various ordinary functions like `filter` with the monadic equivalent often yields interesting results. Implement this function, and then think about what it means for various data types such as `Par`, `Option` and `Gen`.

```
fun <A> filterM(
ms: List<A>,
f: (A) -> Kind<F, Boolean>
): Kind<F, List<A>> = TODO()

```

We don’t have to restrict ourselves to combinators that we’ve seen already. We should take the liberty to explore new solutions too. The combinators we’ve seen here are only a small sample of the full library that `Monad` lets us implement once and for all.