It took us three chapters to get to the moment where we're ready to discuss the origins of the flatMap method in regards to the effects we looked at in Chapter 6, Exploring Built-In Effects. The reason for this is not the complexity of the topic, but the richness of the family of abstractions related to it.
After this introduction, a suspicious reader will think with disappointment—OK, now they are going to use their usual trick and say that there is an abstraction for flatMap, flattener or flatMapative, pull some laws out of thin air, and consider themselves done. What cheaters!
Well, technically we're not cheating because we're not pulling things out of anywhere. Instead, we're taking them from category theory, the branch of mathematics we mentioned previously. The rules our abstractions must obey are defined by mathematicians. There is an advantage to this approach, though—as soon as we can prove that our implementation obeys the required laws, we can use everything that has been proved by category theory to our advantage. One example of this is the possibility of combining two applicatives into one, just like in the example we discussed in the previous chapter.
Going back to our flatMap method, there is still some intrigue there. The abstraction name is Monad, and it is defined by two methods, flatMap, and unit:
import scala.language.higherKinds
trait Monad[F[_]] {
def unit[A](a: => A): F[A]
def flatMap[A, B](a: F[A])(f: A => F[B]): F[B]
}
The monad is defined for a container of type F. The unit method lifts its parameter into the context of F; the flatMap is similar to the plain map method in a sense that it applies f to a. What is different in flatMap and what makes it special is its ability to collapse or flatten two layers of F into one. This is easy to see from the type signatures of a and f.
This possibility to flatten F[F[A]] into F[A] is the reason why monads are often expressed with a different set of methods; that is, map and flatten:
trait Monad[F[_]] {
def unit[A](a: => A): F[A]
def map[A, B](a: F[A])(f: A => B): F[B]
def flatten[A](fa: F[F[A]]): F[A]
}
The flatten method does exactly what we just said—it allows us to reduce the stack of Fs into a single F. Sometimes, the flatten method is also called a join. We will see in a moment why this name makes sense.
Clearly, we have the same situation with monads that we had with applicatives—we can choose the set of primitive functions and implement the rest of functionality in terms of primitives. For instance, the flatMap is equally powerful as a combination of map and flatten, and we can choose one of these combinations.
Let's stick to the initial definition and implement other methods in terms of flatMap. This is what map will look like:
def map[A, B](a: F[A])(f: A => B): F[B] =
flatMap(a)(a => unit(f(a)))
What we're doing here is basically mapping with the function f and lifting the result in context of F as the types require.
Can you remember the name of the abstraction that is characterized by having a map method? Right, this is the functor. Our ability to define a map solely in terms of flatMap for every Monad proves that every Monad is a Functor. Because of this, we can state that Monad extends Functor.
The definition of the flatten method is similarly straightforward:
def flatten[A](a: F[F[A]]): F[A] = flatMap(a)(identity)
With the identity function, we are using part of the flatMap power to convert two layers of F into one without actually doing anything with a.
Can we go further and apply a function that is already in the context of F to the a? It turns out that we can, and we know the method that does this—this is the apply defined in Applicative:
def apply[A, B](a: F[A])(f: F[A => B]): F[B] =
flatMap(f) { fab: (A => B) => map(a) { a: A => fab(a) }}
Here, we're pretending that f is a value, so we just need to represent a as a function that can be applied to this value. The fab function takes a function called A => B that we use to map over the original a, returning B, which becomes an F[B] because of the application of map.
The apply function is also defined in terms of flatMap (and map, which is derived from flatMap) for every monad. This provides evidence that every Monad is an Applicative. Thus, our definition of Monad can be changed into the following form:
trait Monad[F[_]] extends ch08.Applicative[F] {
def flatMap[A, B](a: F[A])(f: A => F[B]): F[B]
def flatten[A](a: F[F[A]]): F[A] = flatMap(a)(identity)
override def unit[A](a: => A): F[A]
override def map[A, B](a: F[A])(f: A => B): F[B] =
flatMap(a)(a => unit(f(a)))
override def apply[A, B](a: F[A])(f: F[A => B]): F[B] =
flatMap(f) { fab: (A => B) => map(a) { a: A => fab(a) }}
}
We can see that the flatMap method is only available for the Monad, not for an Applicative. This leads to interesting consequences, which we will look at later in this chapter.
Now, before switching gears and starting to implement the instances of specific monads, let's discuss the monadic laws first.
Fortunately, there are only two of them, and both are very similar to the functor laws we discussed in the previous chapter; that is, the identity and associativity laws.
The identity law states that applying flatMap and unit should return the original argument. Depending on the order of application, there are left and right identities. We'll represent them formally as usual with ScalaCheck properties (the following snippet does not show the implicit parameters; please consult the accompanying code for the full definition):
val leftIdentity = forAll { as: M[A] =>
M.flatMap(as)(M.unit(_)) == as
}
The left identity stipulates that the result of using flatMap over the argument by lifting it into the context of the monad should be equal to the original argument.
The right identity is a bit more complex:
val rightIdentity = forAll { (a: A, f: A => M[B]) =>
M.flatMap(M.unit(a))(f) == f(a)
}
Basically, the rule is that lifting a into the context and then flatmapping it with some function, f, should produce the same result as applying this function to a directly.
Now, all we need to do is combine both of these properties into a single identity property. We'll need quite a bit of different implicit Arbitrary arguments in order to generate input data, including A, M[A] and A => M[B], but the property itself should be anything but surprising:
import org.scalacheck._
import org.scalacheck.Prop._
def id[A, B, M[_]](implicit M: Monad[M],
arbFA: Arbitrary[M[A]],
arbFB: Arbitrary[M[B]],
arbA: Arbitrary[A],
cogenA: Cogen[A]): Prop = {
val leftIdentity = forAll { as: M[A] =>
M.flatMap(as)(M.unit(_)) == as
}
val rightIdentity = forAll { (a: A, f: A => M[B]) =>
M.flatMap(M.unit(a))(f) == f(a)
}
leftIdentity && rightIdentity
}
The associativity property says that flatmapping using functions in succession should be the same as applying functions in the context of the monad:
forAll((a: M[A], f: A => M[B], g: B => M[C]) => {
val leftSide = M.flatMap(M.flatMap(a)(f))(g)
val rightSide = M.flatMap(a)(a => M.flatMap(f(a))(g))
leftSide == rightSide
})
We'll omit the definition of the implicit parameters for this and a combination rule:
def monad[A, B, C, M[_]](implicit M: Monad[M], ...): Prop = {
id[A, B, M] && associativity[A, B, C, M]
}
Now that we have an understanding of what methods we need to define and how they should behave, let's implement some monads! We'll need to know the internals of the respective containers in order to implement the flatMap. In the previous chapter, we implemented the map method by delegating to the underlying container. Now, we'll use a low-level approach to show that the knowledge of the structure is indeed necessary.
As usual, we will start with the simplest of the standard effects, Option. This is how we implement Monad[Option]:
implicit val optionMonad = new Monad[Option] {
override def unit[A](a: => A): Option[A] = Some(a)
override def flatMap[A, B](a: Option[A])(f: A => Option[B]): Option[B] = a match {
case Some(value) => f(value)
case _ => None
}
}
The implementation of unit should be apparent—the only way to turn A into Option[A] is by wrapping it. Like we did previously, we're using the case class constructor directly to preserve the structure in the case that a is null.
The flatMap implementation is also very transparent—we can't apply a given function to None, and hence we return None as is. In the case that we have provided a is defined, we unwrap the value and apply f to it. This unwrapping is exactly the moment where we're using our knowledge of the internals of Option to flatten the potentially nested result.
We can check that our implementation obeys monadic laws by defining a couple of properties for different types of a and f:. These properties need to be placed in a class extending org.scalacheck.Properties, as usual:
property("Monad[Option] and Int => String, String => Long") = {
monad[Int, String, Long, Option]
}
property("Monad[Option] and String => Int, Int => Boolean") = {
monad[String, Int, Boolean, Option]
}
+ Monad.Monad[Option] and Int => String, String => Long: OK, passed 100 tests.
+ Monad.Monad[Option] and String => Int, Int => Boolean: OK, passed 100 tests.
Given that our properties hold for two different types of a and two different types of functions, we can be pretty sure that our code is correct and proceed with other containers.
For Either, we have a small complication, exactly like we had when we defined a Functor for it - two type parameters instead of one required by the Monad. Are you ready to deal with it the same way as before—by fixing the second type parameter and using the type lambda to define the final type of the monad? The good news is that we won't need to do this! The type lambda is such a common thing that's used in type class programming that many people craved an easier way to do this. This is the projector that plugin was created for. It allows us to use simplified syntax for type lambdas in Scala.
All we need to do so that we can start using the plugin is add the dependency to our project configuration in the build.sbt file:
addCompilerPlugin("org.spire-math" %% "kind-projector" % "0.9.8")
Now that we have this, we can simplify the type lambda syntax from our usual ({type T[A] = Either[L, A]})#T to just Either[L, ?]. The plugin is feature-rich, and we will not go into further details here; visiting the documentation page at https://index.scala-lang.org/non/kind-projector/kind-projector/0.9.7 is highly recommended.
With our new tool, the definition of eitherMonad is easy to read:
implicit def eitherMonad[L] = new Monad[Either[L, ?]] {
override def unit[A](a: => A): Either[L, A] = Right(a)
override def flatMap[A, B](a: Either[L, A])(f: A => Either[L, B]): Either[L, B] = a match {
case Right(r) => f(r)
case Left(l) => Left(l)
}
}
The type class constructor takes a type parameter, L, for the left side of Either. The rest of the implementation should be very familiar by now. It's worth reminding yourself that Either is right-biased—this it the reason we're returning Right from the unit method. It's also worth mentioning the last case in the flatMap pattern match where we repacked l from Left[L, A] into Left[L, B]. This is done to help the compiler infer the correct return type.
For the property definition, we also have to fix a type of the left side. We can do this by defining a type alias, which will improve readability:
type UnitEither[R] = Either[Unit, R]
property("Monad[UnitEither[Int]] and Int => String, String => Long") = {
monad[Int, String, Long, UnitEither]
}
property("Monad[UnitEither[String]] and String => Int, Int => Boolean") = {
monad[String, Int, Boolean, UnitEither]
}
Except for the type alias, the definition of properties is the same as we had for Option.
The definition of Monad[Try] is done by analogy, and we'll leave it as an exercise for the reader.
In contrast, Monad[List] (or Monad[Bucket], if we're to use terms from the previous chapter) is quite different as the List can contain more than one element:
implicit val listMonad = new Monad[List] {
def unit[A](a: => A) = List(a)
def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] = as match {
case Nil => Nil
case a :: as => f(a) ::: flatMap(as)(f)
}
}
The unit is implemented in the same way as the other effects were—just by wrapping its argument. The flatMap is defined in a recursive manner. For Nil, we return Nil. This case is analogous to the case of None in Monad[Option]. In the case of a non-empty list, we have to apply the given function to all of the elements of the list and flatten the result at the same time. This is done in the second matching case.
Let's see if our property holds:
property("Monad[List] and Int => String, String => Long") = {
monad[Int, String, Long, List]
}
property("Monad[List] and String => Int, Int => Boolean") = {
monad[String, Int, Boolean, List]
}
+ Monad.Monad[List] and Int => String, String => Long: OK, passed 100 tests.
+ Monad.Monad[List] and String => Int, Int => Boolean: OK, passed 100 tests.
It looks like it is, but the only reason for this is that the list generator in ScalaCheck does not generate input lists of a significant size. If it did, our property would fail with StackOverflowError because it is not tail-recursive!
Let's fix this by using the techniques that we discussed in Chapter 3, Deep Dive into Functions:
override def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] = {
@tailrec
def fMap(as: List[A], acc: List[B])(f: A => List[B]): List[B] = as match {
case Nil => acc
case a :: aas => fMap(aas, acc ::: f(a))(f)
}
fMap(as, Nil)(f)
}
Now that we have made our implementation tail-recursive by introducing the accumulator, we can safely use it with lists of an arbitrary length. But this approach is still quite direct and slow because of that. On my laptop, this implementation consumed approximately five times more time than the "native" optimized implementation of List's flatMap method. It turns out that this is exactly the case where delegating makes sense:
override def flatMap[A,B](as: List[A])(f: A => List[B]): List[B] = as.flatMap(f)
OK, so we have ignored Future, but have implemented type class instances for all of the containers we discussed in Chapter 6, Exploring Built-In Effects. Are we done with monads? It turns out that we're not—not by a long shot. Just like it's possible to define an indefinite number of applicatives for different types constructors as long as the applicative properties hold, it is possible to do the same with monads.
In the following section, we'll put some widely used monads such as Id, State, Reader, and Writer into code and discuss what are they good for.