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 focal point of this article is the monad, but to fully grasp what it’s about we need to come to terms with the functor on which it relies. A monoid, for example, has a relationship with the semigroup. In fact, we know that the monoid is a semigroup with some additional functionality. Although the relationship between the monad and functor isn’t as clear cut as this, we can still say that a monad is usually a functor too. For this reason this section will help us first understand what a functor is and how to apply it. Once we have laid this foundation, we can advance into the territory of monads with confidence.

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:

 
 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.

 
 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.

Introducing the Monad interface

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.

 
 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.

 
 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.

 
 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

What the monad name means

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.

 
 object Monads {
  
     val genMonad = object : Monad<ForGen> {                  ❶
  
         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.

 
 object Monads {
  
     val parMonad: Monad<ForPar> = TODO()
  
     val optionMonad: Monad<ForOption> = TODO()
  
     val listMonad: Monad<ForList> = TODO()
  
     val listKMonad: Monad<ForListK> = TODO()
  
     val sequenceKMonad: Monad<ForSequenceK> = TODO()
 }
  

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>
  

Monadic combinators

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:

 
 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.

That’s all for this article. If you want to learn more, you can check out the book on our browser-based liveBook reader here.