|
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 aMonoid<B>
to form aMonoid<Pair<A,B>>
, the monoid laws let us conclude that the “fused” monoid operation is also associative. We don’t need to know anything aboutA
andB
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.
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.
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
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
.
Listing 6. Declaring a Monad
instance for Gen
using concrete types
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
:
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.
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.