Monads in Scala Part One: Maybe[Person]

Intro

I've split the introduction to this post into two parts. The first part is long and sentimental, describing my personal journey with monads up to now. The second part is short and to the point. Feel free to skip over the next section if you're not interested in the sappy stuff - you won't be missing anything important.

Sappy Intro

I've been programming Scala for a little over two years now, and I love it. I was an old-time Java hack, firmly embedded in the OO programming paradigm. Scala to me was largely like a souped up Java, with all the clunky, broken things about Java fixed (aside from type erasure). I had taken courses Scheme and the lambda calculus in college, and I thought I had a pretty good understanding of functional programming. However, while programming Scala, and getting exposure to the language, libraries, and community, I began to discover that there is a lot more to functional programming than I originally thought. By far the most prominent example of this was the the importance of the concept of the monad in the Scala community.

I didn't know what a monad was, and over the past couple of years, I've made various efforts to try to understand it. For the most part, the videos I watched, and the articles I read, left me with one of two impressions: Either it didn't make any sense, or I just couldn't see what the big deal was. As I continued to explore, I began to notice that most of the explanatory examples are in Haskell, and not understanding the Haskell language or syntax was a serious impediment for me. At that point, I set out specifically searching for monad examples in Scala, and found this excellent series of blog posts by James Iry: Monads are Elephants (see also parts two, three, and four). Finally, monads were beginning to make sense! But after reading these articles, I realized I was going to have to implement some monads myself to really grok them. I also knew that I would have to follow by example to do this. Which meant that I really needed to bite the bullet and look at some monad examples in Haskell.

No Nonsense Intro

I found an excellent exposition on monads in this Haskell Wikibook, and set out to translate the examples into Scala. In this blog post, we will present a translation of the Maybe/Person example presented in the first page the chapter on monads. In future blog posts, I hope we can do the same for the rest of the pages of this chapter.

A Note on the Code

All the code presented below is based on the Understanding monads page of the Haskell Wikibook. I am very grateful to the authors for making this available. It's very well written! I am also deeply appreciative of the fact that they provide this material under the terms of the Creative Commons License. While I rely heavily on the code presented there, none of it is re-presented here. Most sections of this blog post provide links to the section of the page being discussed. It may help if you read through the wikibook chapter before tackling the Scala presented here, but it isn't strictly necessary.

All the Scala code presented here is my own. The code can be found in this monads-in-scala project on GitHub. I tagged the code as it is presented here as monads-in-scala-1, as I anticipate modifying this code in future blog posts. Be sure to look at the code in src/test/scala tree there as well. Launch sbt in the project, run ~ test, play around and make some edits, and see what happens.

Implementing the Maybe Monad

Let's first translate the definition of the Maybe monad from Haskell into Scala. We'll present the Scala solution first, and then we'll break it down:

Definition of Monad

A monad is defined in the wikibook, and in Wikipedia, as having three parts:

1. A type constructor
2. A unit function, commonly called return in Haskell
3. A binding operation, commonly called >>= in Haskell

How do these elements translate into Scala? Let's examine them one by one.

Type Constructor

In Scala, a type constructor is just the definition of a type that has a type parameter. In our case, the type definition is trait Maybe[+A]. The A is the underlying data type. The + indicates covariance, which means that if an A is a B, then a Maybe[A] is also a Maybe[B]. This is the typical type variance for a container where, once constructed, we can read out what is contained inside, but we cannot write in to the container. In other words, an immutable container.

Because MaybeNot is an empty container, we can use the same MaybeNot instance for all maybes, regardless of the type parameter. To achieve this, we make the type parameter the special Scala type Nothing, which is a sub-type of every other type. Thanks to the covariance of A in Maybe[+A], the type parameter of MaybeNot matches regardless of what is chosen for A.

We use MaybeNot here where the Haskell example uses Nothing, to avoid confusion with Scala's Nothing.

Unit Function

The unit function is a function from the contained type to the container type, i.e., from A to Maybe[A]. The unit function is typically named return in Haskell. A natural place to put a function like this in Scala is as an apply method of a companion object. Because apply methods are automatically generated by the compiler for case classes, we get our unit function for free in method Just.apply(A).

Binding Operation

The binding operation, as a Scala function, would have the following signature:

def bind[A, B](Maybe[A])(A => Maybe[B]): Maybe[B]

In Haskell, this is implemented as a function named >>=. As Scala is an object oriented language, it is natural to implement this as a method on type Maybe[A]. It's also customary to name such Scala methods flatMap.

As you can see, we make use of polymorphism in the above definition of flatMap. This might not please the hard-core functional programmers out there. A non-polymorphic implementation can be achieved with the Scala match operator, and is a more direct translation of the Haskell example:

Maybe Monad Motivation

The initial motivating example for Maybe in the wikibook is a family database where lookups on father and mother may or may not return a result. The wikibook does not define the functions mother and father, but we provide implementations of them in Scala, since we want to be able to test our code. We also provide a list of people to use for testing via companion object method Person.persons. The only thing of note here is that we provide mother and father as instance methods, and not just regular functions:

Maternal Grandfather

The wikibook goes on to explain the usefulness of the Maybe monad by defining a maternalGrandfather function using >>=. What follows is an implementation of maternalGrandfather using flatMap, the equivalent version using match, and a simple test showing the two functions produce the same results.

Both Grandfathers

A similar example follows for bothGrandfathers. This function returns Nothing unless both grandfathers are found. The match version here is greatly simplified by the fact that we can match on two parents at once using pairs.


To demonstrate the usefulness of matching tuples in Scala, let's rewrite the non-flatMap version to avoid matching pairs:

Both Grandfathers Using For

The wikibook proceeds to rewrite the bothGrandfathers example using a Haskell do loop. The Scala equivalent is a for loop, but to make the for loop work, we need to go back and add a map method to Maybe. The equivalent operation to map in Haskell is >>, pronounced then. We can define map in terms of the unit function and the binding operation:

Now we can proceed to write bothGrandfathers using a for loop:

Monad Laws

The wikibook continues by explaining that the unit function and the binding operation cannot be just any old operations; They must obey the three provided laws: left unit, right unit, and associativity. It's obviously not exhaustive and not a proof, but we provide some test code that exercises the three laws with test values. We iterate over all the Person objects in Person.persons to substitute for x. For m, we substitute MaybeNot, plus Just(p) for every p in Person.persons. We take instance method Person.mother as f, and Person.father as g. Here's our test code to help convince ourselves that the monad laws are satisfied:

Monads and Category Theory

The wikibook page on understanding monads concludes with a brief foray into category theory. Two extra functions on monads, fmap and join, are introduced. The Scala equivalent to fmap is map, presented above. The Scala equivalent to join is flatten, which can also be defined in terms of the unit function and the binding operation. However, flatten is tricky to define in Scala, because it requires that the type parameter A is itself a monad. This is achieved in Scala by adding an implicit parameter with type <:<, like so:

To understand this, let's start with the Scaladoc documentation for scala.Predef.<:<, which reads, "An instance of A <:< B witnesses that A is a subtype of B. Requiring an implicit argument of the type A <:< B encodes the generalized constraint A <: B." So the implicit parameter in flatten provides a sort of identity mapping function that maps type Maybe[A] onto type Maybe[Maybe[B]]. The Scala library is designed so that the compiler will guarantee that Maybe[A] is a sub-type of Maybe[Maybe[B]] at any point flatten is called. For instance, the following code:

Just(1).flatten

Will produce the following compiler error:

Cannot prove that maybe.Maybe[Int] <:< maybe.Maybe[maybe.Maybe[B]].

Within the body of flatten, the implicit parameter asMaybeMaybe acts as a type converter from Maybe[A] to Maybe[Maybe[B]]. After performing the type conversion, we simply apply the definition of join as presented in the wikibook. (The identity function is provided in scala.Predef.) Here is a short code sample testing that the flatten implementation is correct:

Monads as Functors

In our example code, we have defined fmap and join (methods map and flatten in Scala) in terms of >>= and return (flatMap and Just.apply in Scala). The concluding section of the wikibook goes on to explain that instead, you could define >>= in terms of fmap and join. Let's see if we can support this claim by writing an alternate flatMap function in these terms, and check that the results are the same as the original flatMap:

Conclusion

It's been an interesting and educational exercise to work through translating these examples from Haskell to Scala. I've gotten a bit more comfortable with Haskell syntax, which should help me out in the future. But having programmed in Scala for over 2 years, I'm already pretty comfortable calling methods like map, flatMap, and collect on an Option. So I'm looking forward to translating the other monad examples in the Haskell wikibook. But before we do that, we'll have to work through two more Maybe examples presented in the next section, which also introduces the <=< operator, which chains functions that return monads.