28 April 2015

Understanding monads is a puzzle with many parts. Understanding the monad interface was easy enough for me, as I'd been programming in functional languages for a while when I first started exploring them, but for a long time I didn't understand how they made IO operations pure. The answer is to add an extra wrinkle, usually glossed over in Haskell oriented sources, by making all IO actions lazy. It this article we're going to explore how this works and undercover some surprising relationships to the free monad, which we have been covering in [recent][free-monad-interpreter] [posts][free-monad-deriving].

We start with a very simple Scala program.

```
println("Monads are the best!")
```

We know that `println`

is impure, meaning it breaks substitution. We can't substitute a call to `println`

with the result of that call (`()`

) without changing the semantics of our program. This is in contrast to pure programs, such as `1 + 2 + 3`

, which we can freely substitute.

Concretely

```
println("Monads are the best!")
```

is not equivalent to

```
()
```

whereas

```
1 + 2 + 3
```

is equivalent to

```
6
```

Our goal is to implement `println`

in such a way that its return value is something that does allow for substitution. I've already hinted we need a monad. But how exactly should this monad be implemented? The solution comes back to the idea we talked about when [introducing the free monad][free-monad-interpreter]: separate the representation and the interpreter.

What we're going to do is make `println`

return an action that, when we run it, really does the printing. An implementation like this will do:

```
object Pure {
def println(msg: String) =
() => Predef.println(msg)
}
```

`Predef.println`

is the "real" `println`

that prints to the console. Our implementation, within `Pure`

, returns a function of no arguments (a thunk) that calls the real `println`

when applied. We can freely substitute calls to `Pure.println`

with the result of calling `Pure.println`

. In other words

```
Pure.println("Monads are the best!")
```

is equivalent to

```
() => Predef.println("Monads are the best!")
```

We have an implementation that maintains substitution, which is a step forward. But to make this implementation useful we need two more things:

- we must somehow tie together our uses of
`println`

, so we don't just have thunks randomly littered throughout our code; and - at some point we must actually run these thunks to print stuff out.

We can solve both these problems by defining a monadic API for IO actions. This involves changing the representation from a function to a data type with an implementation of `flatMap`

and a method `run`

. I recommend undertaking this exercise yourself. It's a bit more subtle than I thought it would be; the main issue is defining `flatMap`

without running actions prematurely.

Here's an example to get you started. Your code *should not* print anything until `Example.run`

is called.

```
object Example {
val io =
for {
_ <- Pure.println("Starting work now.")
// Do some pure work
x = 1 + 2 + 3
_ <- Pure.println("All done. Home time.")
} yield x
def run =
io.run
}
```

Here's my solution:

```
object Pure {
sealed trait IO[A] {
def flatMap[B](f: A => IO[B]): IO[B] =
Suspend(() => f(this.run))
def map[B](f: A => B): IO[B] =
Return(() => f(this.run))
def run: A =
this match {
case Return(a) => a()
case Suspend(s) => s().run
}
}
final case class Return[A](a: () => A) extends IO[A]
final case class Suspend[A](s: () => IO[A]) extends IO[A]
object IO {
def point[A](a: => A): IO[A] =
Return(() => a)
}
def println(msg: String): IO[Unit] =
IO.point(Predef.println(msg))
}
```

The key problem, as I mentioned above, is implementing `flatMap`

. With an object of type `IO[A]`

and a function of type `A => IO[B]`

, it seems that we must run the `IO[A]`

to get the `A`

to apply to the function. However, once we run actions we break substitution. The solution is to introduce a separate case to our algebraic data type to represent a call to `flatMap`

without actually running anything. This is the `Suspend`

case in my implementation.

Avid readers of the blog will recognise that this is almost exactly the algebraic data type we used when [deriving the free monad][free-monad-deriving]! That's no accident. The free monad is all about [separating the structure of the computation from the interpreter that gives it meaning][free-monad-interpreter]. *We are doing exactly the same thing here.* The structure of the computation is represented by the algebraic data type, and we give meaning to the structure when we `run`

it.

This is a fairly simple example, but I found a surprising number of lessons in it.

The first is the trick of making IO pure by *not doing any IO* (until we `run`

the code). This trick is very useful. It's the same implementation technique used in Scalaz's [`Task`

] (a better alternative to `Future`

) and in the free monad.

We can't maintain substitution after we run our IO actions. The way Haskell handles the `IO`

monad is to only allow the runtime to run it (with the exception, I believe, of `unsafePerformIO`

). Therefore all programs are pure from the programmer's point of view. In Scala we just have to be careful to separate the two phases so we don't try to use substitution of actions after they've been run.

The idea of representing actions as data is very general. I've explored this point in depth in the [prior post][free-monad-interpreter] introducing the free monad. We've seen another example here. We're also seeing the same implementation pattern come up again. So as a general point, if you find yourself implementing some monad variant and you don't want to use the free monad, you probably need an algebraic data type like the one we just saw.

In some sense the representation of monads in terms of `map`

and `join`

(described [previously][free-monad-interpreter]) is more primitive than the one in terms of `flatMap`

. With this representation we build nested structured like `IO[IO[IO[C]]]`

through repeated application of `map`

, and we then reduce these back to just, say, `IO[C]`

using `join`

. We can view `map`

as sequencing actions to perform, and `join`

as performing them.

Finally, we can derive a useful lesson about monad composition in the free monad. If you know about monad transformers, you'll know they are one approach to composing monads. It's fairly common to define a "monad stack" that is used consistently throughout an application. For example, an application I'm currently writing uses

```
type Result[Error, Success] = EitherT[Task, Error, Success]
```

The free monad offers another approach to monad composition, via the [a la carte][a-la-carte] technique. The question then becomes, if we use the free monad should we raise all our monads into it, in the same way we do with monad transformers? So far I have not done this. My approach has been to put IO actions into the free monad but leave other monads (e.g. `Option`

and `\/`

) out of it. This means occasionally seeing nested `for`

comprehensions but I find it simpler and more performant to work this way. One caveat: I haven't written a great deal of code using the free monad so my opinion might change.

[free-monad-interpreter]: {% post_url 2015-04-13-free-monads-are-simple %}
[free-monad-deriving]: {% post_url 2015-04-23-deriving-the-free-monad %}
[`Task`

]: http://docs.typelevel.org/api/scalaz/nightly/#scalaz.concurrent.Task
[a-la-carte]: http://www.cs.ru.nl/~W.Swierstra/Publications/DataTypesALaCarte.pdf