Thursday, February 14, 2013

Looneysquash's Obligatory Monad Tutorial

I've been learning a lot about Scala lately. Also I previously read a lot about Haskell. It turns out that in both of those language communities, it's obligatory to write a tutorial on Monads.

I will mostly be using Scala for this tutorial.

Update: I empathized map over flatMap. It's been pointed out to me that it's flatMap that makes a monad a monad, and that map only makes it a functor.

What's a Monad?

A monad is a type that implements certain methods. In Scala, those methods are map and flatMap

A monad is a container type. It's a type that contains some other value. Examples would be Option, which contains exactly zero or one values, and List, which contains zero or more values.

A type that's a monad is normally parameterized. That is, it has a type parameter, and is written List[A] in Scala, or List<T> in Java.

What does map do?

Back in C, we have something called a function pointer. Often, a function would take a function pointer as one of it's arguments. We would refer to that argument as a "callback". The function was often a library function like sort, and the function pointer let sort call back into our own code.

In Scala, we don't have pointers. But we do have functions that take other functions as arguments. They're called "higher order functions". And map is a higher order function. 

So for List[A], map looks like this:  def map[B](f: (A) => B): List[B]

What this means is map is a method of the List class, it takes a single parameter named f, and returns a new List. The B in List[B] means the new List can be a list of something different than the original list, whose type we said is List[A]

The single parameter, f, is itself a function, and f takes a single paramater. That parameter has to be the same type as the list. So if we had a List[Int], the parameter must be Int. It returns a new value. That new value can be of any type, and we're going to call its type B. That new type determines the type of list that is returned by map. So if f returns a String, map returns a List[String].

What does f do? Anything it wants. That's the beauty of callbacks. You can write a function to do anything you want, and call map with that function. Then your function gets called once for each element in the list. map builds a new list with the return values of your function, and returns to you the new list.

Here's a simple example.
val list = List(1, 2, 3)
val listTimes42 = => x * 42)

One interesting thing to note here, is what happens if the list is empty. The answer is nothing. Your callback is never called, and a new empty list is returned. It kind of reminds me of how short circuiting works with the && operator in most languages.

So what are monads good for?

Monads are actually good for a surprising variety of things. Obviously, map is great if you need to turn A's into B's. But monads turn out to be useful for error handling too. Remember how I said running map on an empty list does nothing? That works with Option too.

If you're not familiar with Option[A], it's basically an abstract base class with two concrete child classes: Some[A], and None. It's a collection that contains zero or one element.

In Scala, Option is used instead of null. Scala still has null for Java compatibility, but actual Scala code almost always uses Option instead. Unlike null, Option forces you to check which subclass you actually have. This goes a long way in catching at compile time what would be NullPointerExceptions at runtime in Java, or segfaults in C.

If you come from C, then you know one way to deal with null, if statements. if (ptr == NULL) return; Or if (ptr != NULL) { /* run a block of code */ }. If ptr is a struct that contains a pointer to another struct that might also be null, which contains a pointer to a third struct which might also be null, things get ugly pretty fast. You either have nested if's and deeply indented code, or multiple early returns.

In Java, you can use the method I just described, or you use try/catch and attempt to catch the NullPointerException that will get if you dereference the null pointer.

But with Option, you can do something like this:
  case class User(address: Option[Address])
  case class Address(street: Option[Street])
  case class Street(number: Option[Int])
  val user = Some(User(Some(Address(Some(Street(Some(123)))))))
  val user2: Option[User] = None;
  val streetNumber = user flatMap { _.address flatMap { _.street map { _.number }}}

If you're not used to reading Scala code, here's a couple of hints. Semicolons are allowed but not required. Types come after variable names, separated by a colon. You can call any method as an infix operator, so "user flatMap { lambda }" is just another way of writing "user.flatMap({ lambda })". The underscore represents the lambda's parameter, and is a shortcut to avoid giving the lambda's parameter a name.

The variable streetNumber is now Some(123). But if we had used user2, streetNumber would be None. The getOrElse() method does what you think does, it returns the value of the Option, but if the Option is None, it returns it's argument.

One new thing I introduced here is the use of flatMap. It works similar to map, but it flattens it's return value. It is the reason we end up with an Option[Int] and not an Option[Option[Option[Int]]].

Scala provides syntactic sugar nested calls to map and flatMap. It does so with what's called a for comprehension. Here is the previous example rewritten to use a for.
  val streetNumber = for {
    u <- user
    address <- u.address
    street <- address.street
    number <- street.number
  } yield number

This translates to the previous example, and streetNumber ends up as Some(123) with the type Option[Int]. But if anything in here had been None, it would have short circuited to be None.

Monads are like a semicolon operator

Scala doesn't need them, but lets pretend you added semicolons to the previous example:
  val streetNumber = for {
    u <- user;
    address <- u.address;
    street <- address.street;
    number <- street.number
  } yield number

The code for map or flatMap runs where the semicolons are. That means when you define your own classes with their own map methods, and then use them in a for, you are essentially overriding the semicolon operator! You're not just reading between the lines, you're executing between the lines.

The Future is monadic

It turns out that map doesn't have to run your supplied callback immediately. There is a monad called Future. You can read more about it here. A Future represents a value that might not be available yet. Some other thread is off computing the value, and since it runs asynchronous from you, it might or might not be finished running yet.

Now, you could call it's get() method, and block your thread until the computation completes. But, you could instead call map(). That will return to you a new Future that consists of the first future, but with your function applied to it. You can use multiple calls to map, or a for statement, to build up a complex set of actions, all of which run only once the value of the Future is available.

Better still, there might be several Futures involved. The monad style allows you to write your code as if it was simple sequential operations, without blocking, and with automatic short circuiting if any piece along the way fails.

Haskell uses it for I/O

In Haskell, I/O is done using monads. Unlike Scala, Haskell considers itself to be a pure functional language, which means there are no side effects, and every function's return value depends only upon it's parameters.

So what Haskell does is define a special monad named IO. IO contains a value, but there's no safe way to get the value out of the IO container. Instead, you are forced to call >>=, pronounced "bind", which is Haskell's version of flatMap. So you can't get the value out of the box, but you can pass in your own functions, which run inside the box.

Similar to how you can build up a computation with the Future monad that doesn't run until the background thread completes, you can build up a computation with the IO monad using only pure code, and that computation can then be executed by the Haskell runtime.

The chained callback code that the monadic style forces you to use also has another benefit in Haskell, it forces an order on your statements, which would otherwise be free to run in any order in Haskell.

Further Reading

1 comment:

  1. This comment has been removed by the author.