## Monads, composition and the order of computation

Question

All the monad articles often state, that monads allow you to sequence effects in order.

But what about simple composition? Ain't

``````f x = x + 1
g x = x * 2

result = f g x
``````

requires `g x` to be computed before `f ...`?

Do monads do the same but with handling of effects?

Show source
2016-12-24 05:12 3 Answers

## Answers to Monads, composition and the order of computation ( 3 )

1. Yes, monads use function composition to sequence effects, and are not the only way to achieve sequenced effects. In most languages there is sequencing by strict semantics applied first to the function side of an expression, then to each argument in turn, and finally the function is applied to the arguments. And that works for those languages. And if you're looking at monads for their purpose you are probably going to come out of the situation upset because they come from abstract mathematics and so it rapidly becomes asking something like, what is the purpose of squares?

A monad is a pattern. The pattern is, sometimes you have an adjective which does not add much when you repeat it. For example there is not much added when you say "a delayed delayed x" or "zero or more (zero or more xs)" or "either a null or else either a null or else an x." Similarly for the IO monad, not much is added by "a program to compute a program to compute an x" that is not available in "a program to compute an x."

The pattern is that there is some canonical merging algorithm which merges:

``````join: given an <adjective> <adjective> x, I will make you an <adjective> x.
``````

If this is the case then you can (generally pretty easily) add two nice features: first the mapping, which says:

``````map: given an x -> y and an <adjective> x, I will make you an <adjective> y
``````

and second the embedding, which says:

``````return: given an x, I will make you an <adjective> x.
``````

Given these three things and a couple axioms you happen to have a common "monad" idea which you can develop One True Syntax for.

Someone at some point noticed, "oh, in order to get impure effects from pure code I need to do metaprogramming, which means one of my types needs to be "programs which compute an X." What can I do with them? Well the biggest thing is, I need to be able to bring the business logic back into the Haskell universe even when effects are flying every which way. And this means I want to take a program that computes an X and a function which takes an X and produces the next program, a program that computes a Y, and somehow glue them together into a program which computes a Y." The IO monad was born. Why? Because with one more (embedding) operation, that `bind` operation admits of a mapping and a merging idea, and the axioms in general transfer over very nicely.

Someone else figured out that the axioms we were expecting from these monads were just category axioms for the `a -> <adjective> b` functions: associativity and the unit element in the form of the embedding arrow. So the theory got super-simple after a bit of work. The category in question is called the "Kleisli" category and categories in general are like gussied-up monoids.

2. Yes, the functions you proposed are strict for the standard numerical types. But not all functions are! In

``````f _ = 3
g x = x * 2
result = f (g x)
``````

it is not the case that `g x` must be computed before `f (g x)`.

3. Disclaimer: Monads are a lot of things. They are notoriously difficult to explain, so I will not attempt to explain what monads are in general here, since the question does not ask for that. I will assume you have a basic grasp on what the `Monad` interface is as well as how it works for some useful datatypes, like `Maybe`, `Either`, and `IO`.

# What is an effect?

Your question begins with a note:

All the monad articles often state, that monads allow you to sequence effects in order.

Hmm. This is interesting. In fact, it is interesting for a couple reasons, one of which you have identified: it implies that monads let you create some sort of sequencing. That’s true, but it’s only part of the picture: it also states that sequencing happens on effects.

Here’s the thing, though… what is an “effect”? Is adding two numbers together an effect? Under most definitions, the answer would be no. What about printing something to stdout, is that an effect? In that case, I think most people would agree that the answer is yes. However, consider something more subtle: is short-circuiting a computation by producing `Nothing` an effect?

## Error effects

Let’s take a look at an example. Consider a the following code:

``````> do x <- Just 1
y <- Nothing
return (x + y)
Nothing
``````

The second line of that example “short-circuits” due to the `Monad` instance for `Maybe`. Could that be considered an effect? In some sense, I think so, since it’s non-local, but in another sense, probably not. After all, if the `x <- Just 1` or `y <- Nothing` lines are swapped, the result is still the same, so the ordering doesn’t matter.

However, consider a slightly more complex example that uses `Either` instead of `Maybe`:

``````> do x <- Left "x failed"
y <- Left "y failed"
return (x + y)
Left "x failed"
``````

Now this is more interesting. If you swap the first two lines now, you get a different result! Still, is this a representation of an “effect” like the ones you allude to in your question? After all, it’s just a bunch of function calls. As you know, `do` notation is just an alternative syntax for a bunch of uses of the `>>=` operator, so we can expand it out:

``````> Left "x failed" >>= \x ->
Left "y failed" >>= \y ->
return (x + y)
Left "x failed"
``````

We can even replace the `>>=` operator with the `Either`-specific definition to get rid of monads entirely:

``````> case Left "x failed" of
Right x -> case Left "y failed" of
Right y -> Right (x + y)
Left e -> Left e
Left e -> Left e
Left "x failed"
``````

Therefore, it’s clear that monads do impose some sort of sequencing, but this is not because they are monads and monads are magic, it’s just because they happen to enable a style of programming that looks more impure than Haskell typically allows.

## Monads and state

But perhaps that is unsatisfying to you. Error handling is not compelling because it is simply short-circuiting, it doesn’t actually have any sequencing in the result! Well, if we reach for some slightly more complex types, we can do that. For example, consider the `Writer` type, which allows a sort of “logging” using the monadic interface:

``````> execWriter \$ do
tell "hello"
tell " "
tell "world"
"hello world"
``````

This is even more interesting than before, since now the result of each computation in the `do` block is unused, but it still affects the output! This is clearly side-effectful, and order is clearly very important! If we reorder the `tell` expressions, we would get a very different result:

``````> execWriter \$ do
tell " "
tell "world"
tell "hello"
" worldhello"
``````

But how is this possible? Well, again, we can rewrite it to avoid `do` notation:

``````execWriter (
tell "hello" >>= \_ ->
tell " " >>= \_ ->
tell "world")
``````

We could inline the definition of `>>=` again for `Writer`, but it’s too long to be terribly illustrative here. The point is, though, that `Writer` is just a completely ordinary Haskell datatype that doesn’t do any I/O or anything like that, and yet we have used the monadic interface to create something that looks like ordered effects.

We can go even further by creating an interface that looks like mutable state using the `State` type:

``````> flip execState 0 \$ do
modify (+ 3)
modify (* 2)
6
``````

Once again, if we reorder the expressions, we get a different result:

``````> flip execState 0 \$ do
modify (* 2)
modify (+ 3)
3
``````

Clearly, monads are a useful tool for creating interfaces that look stateful and have a well-defined ordering despite actually just being ordinary function calls.

# Why can monads do this?

What gives monads this power? Well, they’re not magic—they’re just ordinary pure Haskell code. But consider the type signature for `>>=`:

``````(>>=) :: Monad m => m a -> (a -> m b) -> m b
``````

Notice how the second argument depends on `a`, and the only way to get an `a` is from the first argument? This means that `>>=` needs to “run” the first argument to produce a value before it can apply the second argument. This doesn’t have to do with evaluation order so much as it has to do with actually writing code that will typecheck.

Now, it’s true that Haskell is a lazy language. But Haskell’s laziness doesn’t really matter for any of this because all of this code is actually pure, even the example using `State`! It’s simply a pattern that encodes computations that look sort of stateful in a pure way, but if you actually implemented `State` yourself, you’d find that it just passes around the “current state” in the definition of the `>>=` function. There’s not any actual mutation.

And that’s it. Monads, by virtue of their interface, impose an ordering on how their arguments may be evaluated, and instances of `Monad` exploit that to make stateful-looking interfaces. You don’t need `Monad` to have evaluation ordering, though, as you found; obviously in `(1 + 2) * 3` the addition will be evaluated before the multiplication.

# But what about `IO`??

Okay, you got me. Here’s the problem: `IO` is magic.

Monads are not magic, but `IO` is. All of the above examples are purely functional, but obviously reading a file or writing to stdout is not pure. So how the heck does `IO` work?

Well, `IO` is implemented by the GHC runtime, and you could not write it yourself. However, in order to make it work nicely with the rest of Haskell, there needs to be a well-defined evaluation order! Otherwise things would get printed out in the wrong order and all sorts of other hell would break loose.

Well, it turns out the `Monad`’s interface is a great way to ensure that evaluation order is predictable, since it works for pure code already. So `IO` leverages the same interface to guarantee the evaluation order is the same, and the runtime actually defines what that evaluation means.

However, don’t be misled! You don’t need monads to do I/O in a pure language, and you don’t need `IO` to have monadic effects. Early versions of Haskell experimented with a non-monadic way to do I/O, and the other parts of this answer explain how you can have pure monadic effects. Remember that monads are not special or holy, they’re just a pattern that Haskell programmers have found useful because of its various properties.