|
|
| Rubik’s Cube, color scheme modified, with shadow and reflection (Photo credit: Wikipedia) |
A monad is just a monoid in the category of endofunctors, what’s the problem? I like this quote. When you find it funny you probably understand what a monad is. And I’ll try to explain it.
Learning this stuff was kinda hard for me because I’ve never encountered category theory so the concepts seemed strange to me. Now I’ll try to share my intuition and hopefully help somebody. Pro tip: read many different “monad tutorials”. Number of these articles is apparently exponential function so you won’t have trouble finding them. I’ll try to deliver a more pragmatic approach so instead of formally correct definitions I’ll do some hand-waving to produce something more useful.
Types(and kinds)
Instead of talking about categories and morphisms let’s focus on types. That’s what scala is about right?
We are talking about general concepts and transformations(functions) here so we’ll need generics. The other point is we want to have different semantic for different occasions. The most obvious way to do that is to write different generic wrappers. More formally: type constructors. Stuff like Option[A], List[A], Future[A], Box[A]… These are not usable types yet(roughly speaking) as scala doesn’t support raw types like java. You need to provide type parameters to obtain types like Option[Int], List[Option[String]]… We say that such types are higher kinded types. See a kind is to type what a type is to value. Remember that, it’s a great analogy(from Daniel Spiewak). So Option, List and other types we are currently interested in are of kind * -> *. This reads “type to type”. It takes a type parameter, say Int, and produces a type, in this case Option[Int].
It should slowly become clear that we can write a higher kinded type to add custom semantics to any raw type.
Functors
Function maps from value a to value b. A functor is a higher kinded type that allows to lift functions and operate on boxed values. This means function does not need to be aware of any additional semantics you put in place. In other words, a functor is something that has a proper map function.
trait Functor[F[_],+A]{
def map[B](f: A=>B): F[B]
}
So the functor “knows” about the type of box(F[_] is scala syntax for * -> *) and takes type parameter. Map must then be implemented to lift a function into this context. A sample usage. Re-implementing Option type
sealed trait Opt[+A] extends Functor[Opt, A]
case class Som[A](value: A) extends Opt[A]{
def map[B](f: A=>B) = Som(f(value))
}
case object Non extends Opt[Nothing]{
def map[B](f: Nothing=>B) = Non
}
Option adds semantics of missing value. Box may be full or empty. And computations must succeed in any case. Operations on empty option(Non) just return an empty box while if there is a value you apply the function to the value and box it up.
Most know application of map is probably on List. It transforms the List[A] to List[B] by applying the function to every element.
Code above is in fact an endofunctor. Endofunctor is something that maps from category A to category A. A in this case is the category of types. There are links at the bottom for more explanation.
Typeclasses
This comes from functional languages(I’ve learned it from Haskell first). It’s a simple concept in it’s heart. Ad-hoc polymorphism. Add functionality and semantics to existing types without changing them. You do that by creating a type class and instances for types you want to “extend” the type class. First of all type class has nothing in common with classes. I’ll rewrite the Opt type sample with type classes to make an example.
trait Functor[F[_]]{
def map[A,B](fa: F[A])(f: A=>B): F[B]
}
sealed trait Opt[+A]
case class Som[A](value: A) extends Opt[A]
case object Non extends Opt[Nothing]
implicit object OptFunctor extends Functor[Opt]{
def map[A,B](opt: Opt[A])(f: A=>B) = opt match {
case Non => Non
case Som(a) => Som(f(a))
}
}
you pull the Functor instance from the implicit scope implicitly[Functor[Opt]] or do view bounds
def functorId[F[_] : Functor](fa: F[_]) = fa
here functorId is identity function that doesn’t compile if functor instance doesn’t exist for it’s argument.
Monoids
I’ve included type classes because monoids are much easier expressed through them. Object oriented way gets messy. You can try. Or better – prove me wrong, I’ll be delighted.
So a monoid is something that can be added togheter or combined in a way. That’s it. Oh and it needs an identity element. Let’s express that as a type class
trait Monoid[M]{
def id: M
def dot(a: M, b: M): M
}
and an instance for Int with example usage
implicit object IntSumMonoid extends Monoid[Int]{
val id = 0
def dot(a: Int, b: Int) = a+b
}
def combine[A](xs: List[A])(implicit monoid: Monoid[A]) =
xs.fold(monoid.id)( (a,b) => monoid.dot(a,b) )
// combine(List(1,2,3)) == 6
You could easily do multiplication instead by setting id to 1 and replacing + with *.
Monads
Let’s stay with options and lists for a bit. What if you have a function f that returns an option(f: A=>Option[B])? If you map it over an option you get Option[Option[B]] or even more levels.
You can deal with this by pattern matching…
def twoLevels[A,B](o: Opt[A])(f: A=>Opt[B]) = o match {
case Non => Non
case Some(value) => f(value)
}
and this produces the desired result. Same goes for list. You get into situations where you want List[A] but you got List[List[A]]. You can solve this by flattening the list(List has method flatten but let’s demonstrate it here)
def flatten[A](xss: List[List[A]]): List[A] = xss match {
case Nil => Nil
case ys::yss => ys:::flatten(yss)
}
Again pattern matching. What do these two got in common? You do something depending on the current value, execute the transformation(or not) and do something with the output. Looks very similar to the map function. And it is. On lists it’s just map and then flatten. Literally, you can write this with scala collections. But you can also do it in a single function. Scala calls it flatMap because of what it does. In haskell world it’s bind, we’ll see why in a minute. Here’s the type signature
trait Monad[M[_]]{
def flatMap[A,B](ma: M[A])(f: A => M[B]): M[B]
}
and an instance for our options. Note that Opt class did not need to be changed.
implicit object OptMonad extends Monad[Opt]{
def flatMap[A,B](ma: Opt[A])(f: A => Opt[B]): Opt[B] =
ma match {
case Non => Non
case Som(a) => f(a)
}
}
So why is this useful? If you have instances for collections(like in scalaz, standard collections do this in OO way) you can abstract away pattern matching and have very readable code. If you want do chain failable computations you just wrap them up in options and do a for expression. Like this
val result = for{
a <- Option(foo()) //foo can return null
b <- Option( bar(a) ) //bar can null too
c <- baz(b) //baz returns an option
} yield computation(c) // 'computation' never fails
What’s the type of result? Option of whatever computation returns. All failures are abstracted away.
Another good thing about flatMap is that it can express map and filter too. And that’s the reason for expressions from scala can be called monadic comprehensions.
Semantics
What’s so cool about sytactic sugar for pattern matching that it deserves such a special place? Monads are much more. Inside the for comprehension you have a custom programming language defined by the monad – the implementation of flatMap for given type. See, as long as it obeys some laws, the binding function can do pretty much anything.
Let’s take a look at IO monad. There’s nothing scary here, you have ‘boxes’ describing IO actions. Let’s refer to these as contexts. And you can bind them together. If I have a ReadLine action and bind PrintLine action over it I’ll get a new action that will echo a line of text. Code would look something like this
for{
input <- ReadLine()
} yield PrintLine(input)
Note the initials. ReadLine and PrintLine are case class constructors. This expression just returns an IO action it doesn’t perform it – this is up to the caller. And so this expression is referentially transparent(always returns the same output for same input and no side effects). How does it work? Scala compiler actually desugars it into
ReadLine().flatMap( input => PrintLine(input) )
And flatMap is inplemented to join the actions together. See this is a great way to write functional programs that look imperative. In fact it’s the only way to do IO in haskell. Scala is more forgiving in this way.
What about futures? Future is a box that will hold a value sometime in the future. Scala 2.10 has them, Akka had them before and I think they’re in scalaz too. Heck even java standard library has them. Java one is not a monad though. Fun thing about monadic futures is that you can compose them.
for{
a <- futureA
_ <- futureB
c <- futureC
} yield a+c
This will yield a new future. It will wait on futureA to complete, take it’s value, wait for futureB(for side effects probably) and then wait on c for its value and on completion it will hold the sum. Different futures can be executed in parallel, even on different machines yet you can compose them and work with them in a sequential – very imperative – way. This works especially well with non-blocking IO since monadic comprehensions don’t block(if flatMap has a sane implementation).
Monoid in category of endofunctors
The joke from the beginning of course. Stop reading for a moment and think about it. It should make sense. If it doesn’t – read ahead.
Monad binds(combines) functions over a value in a context. And it adds some semantics while combining them. I tried writing some code
object OptTransMonoid {
def id[A] = (a:A) => Som(a)
def dot[A,B,C](f: A=>Opt[B], g: B=>Opt[C]) = (a:A) => {
f(a) match {
case Non => Non
case Som(a) => g(a)
}
}
}
You can see that I didn’t extend the monoid trait. I just couldn’t come up with a proper type parameter. Problem is that the two transformations we are trying to compose are of different types. So you need a generic method to remain typesafe. And a generic method cannot override a non-generic one on JVM. No matter how hard you try with type parameters. But the principle holds. A monad over M is a monoid over _=>M[_] (this is hand waving and not formally correct. _ stands for “some type” not Any).
More material
This concludes my brief overview. I hope you grew to like functional stuff. I’ve written a small IO monad implementation and usage demonstration below to give you a feel for real life usage.
IO Monad sample
trait IOAction[A]{
outer =>
def run: A
def map[B](f: A=>B) = new IOAction[B]{
def run = f(outer.run)
}
def flatMap[B](f: A=>IOAction[B]) = new IOAction[B]{
def run = f(outer.run).run
}
}
case object ReadLine extends IOAction[String]{
def run = readLine()
}
case class PrintLine[A](s: A) extends IOAction[Unit]{
def run = println(s.toString)
}
val greeter = ReadLine.flatMap(name => PrintLine("hello " + name))
greeter.run //reads a line and greets you
//with sugar(and nice to user)
val niceGreeter = for{
_ <- PrintLine("who are you?")
name <- ReadLine
_ <- PrintLine("hello " + name)
} yield ()
niceGreeter.run
Just a quick note. Monadic comprehension is this way because desugaring of <- is flatMap except for the last one where it's map. So to work around this you need to yield () instead of yielding the println action as this will map it instead of flatMap.
