When you're starting to use functional programming libraries in scala there is something which might not feel right to you. But you suppress that feeling because everything seems to work just a fine. You try to move on, but a question is racing through your head. I'm talking of course about:
Why the hell can I call
flatMapandmapon my data types, even though it isn't implemented on my data types?
Consider a small example. We will write our own mirror of the Option data type. The original Option has two cases, Some(a) if there is a value and None if there is none. Let's call our data type Maybe which the cases Just(a) and Empty.
sealed trait Maybe[+A]
final case class Just[A](a: A) extends Maybe[A]
case object Empty extends Maybe[Nothing]So far, so good. Since we know that Option is a monad, Maybe should be too. Let's encode that by using the following Monad type class:
trait Monad[F[_]] {
def unit[A](a: A): F[A]
def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
}A simple monad type class, giving us unit and flatMap for our F. Let's give a Monad instance to our Maybe type.
object Maybe {
implicit val maybeMonad = new Monad[Maybe] {
def unit[A](a: A): Maybe[A] = Just(a)
def flatMap[A, B](fa: Maybe[A])(f: A => Maybe[B]): Maybe[B] =
fa match {
case Empty => Empty
case Just(a) => f(a)
}
}
}What do we have here? We are defining an implicit instance of the type Monad[Maybe] on the companion object of our type. This instance implements unit by wrapping the given value a within a Just. And it implements flatMap just as it is defined on Option, namely: if we get an Empty, return an Empty. Otherwise, take the value within the monad and pass it to the given function f.
Okay, so here's the problem: If flatMap is not defined on Maybe[X], but only on Monad[Maybe], why can I call flatMap if I have only something of type Maybe[X]? Or phrased differently, why does this compile:
val a: Maybe[Int] = Just(3)
a.flatMap(i => Just(i + 3))It shouldn't, because there is no flatMap on Maybe[Int]. And behold, it doesn't compile. But there is a way to get it to compile and this is how functional programming libraries do it. Whenever the compiler reaches a point where it can't compile something because a method seems to be missing on some type, it doesn't just give up. Instead, it searches for an implicit class (or def) which turns the type into something that has the method the compiler needs. Another quick example.
println(3.triple) doesn't compile. But if you have defined an implicit class like the following, it compiles just fine.
implicit class IntOps(i: Int) {
def triple: Int = i * 3
}When compiler tries to call triple on an Int and fails, it searches for an implicit class (or def) which takes an Int and turns it into something which has this method defined. The IntOps class matches the requirements exactly. It takes an Int, it is marked as implicit and it has the needed method defined. So the compiler rewrites our code into something equivalent to println(IntOps(3).triple) which compiles and works.
Our use case with monads is a bit more complicated, but not by much. When we write a.flatMap(i => Just(i + 3)), the compiler fails to resolve method flatMap on a. So it now looks for an implicit class (or def) which takes a Maybe[Int] and adds the flatMap operation. We can provide such a class like so:
implicit class MonadOps[F[_], A](fa: F[A])(implicit ev: Monad[F]) {
def flatMap[B](f: A => F[B]): F[B] = ev.flatMap(fa)(f)
}Now there are a few things here. First of all, our implicit class doesn't take a Maybe[Int] but an F[A]. This isn't a problem. As long as the compiler can unify the types, we are fine. In this case, we can substitute F[_] with Maybe[_] and A with Int to get our types to align. This leaves us with MonadOps(fa: Maybe[Int]) which is exactly what we need.
The other thing that's different is that we are requiring another parameter of type Monad[F]. That's not a problem either, because the compiler sees that the parameter is marked with implicit. It then searches for instances of the type F marked with implicit themselves. Such implicit resolution always looks on the companion object of the type we need for implicit instances. Since the compiler substituted F with Maybe, it searches on object Maybe {...} for the implicit instance. Where it finally finds it.
In the end, the compiler rewrites our initial code (a.flatMap(i => Just(i + 3))) to something along the lines of MonadOps[Maybe, Int](a)(Maybe.maybeMonad).flatMap(i => Just(i + 3)).
And this is how flatMap gets onto our data types. Here is the complete code if you want to play with it:
object Main {
trait Monad[F[_]] {
def unit[A](a: A): F[A]
def flatMap[A, B](fa: F[A])(f: A => F[B]): F[B]
}
implicit class MonadOps[F[_], A](fa: F[A])(implicit ev: Monad[F]) {
def flatMap[B](f: A => F[B]): F[B] = ev.flatMap(fa)(f)
}
sealed trait Maybe[+A]
final case class Just[A](a: A) extends Maybe[A]
case object Empty extends Maybe[Nothing]
object Maybe {
implicit val maybeMonad = new Monad[Maybe] {
def unit[A](a: A): Maybe[A] = Just(a)
def flatMap[A, B](fa: Maybe[A])(f: A => Maybe[B]): Maybe[B] =
fa match {
case Empty => Empty
case Just(a) => f(a)
}
}
}
def main(args: Array[String]): Unit = {
val a: Maybe[Int] = Just(3)
println(a.flatMap(i => Just(i + 3)))
}
}