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?

Answer 1

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 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.

Answer 2

Yes, monads use function composition to sequence effects, and are not the only way to achieve sequenced effects.

Strict semantics and side 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. So in JS, the function application form,

<Code 1>(<Code 2>, <Code 3>)

runs four pieces of code in a specified order: 1, 2, 3, then it checks that the output of 1 was a function, then it calls the function with those two computed arguments. And it does this because any of those steps can have side-effects. You would write,

const logVal = (log, val) => {
  console.log(log);
  return val;
};
logVal(1, (a, b) => logVal(4, a+b))(
  logVal(2, 2),
  logVal(3, 3));

And that works for those languages. These are side-effects, which we can say in this context means that JS's type system doesn't give you any way to know that they are there.

Haskell does have a strict application primitive, but it wanted to be pure, which roughly means that it wanted the type system to track effects. So they introduced a form of metaprogramming where one of their types is a type-level adjective, “programs which compute a _____”. A program interacts with the real world; Haskell code in theory doesn't. You have to define “main is a program which computes a unit type” and then the compiler actually just builds that program for you as an executable binary file. By the time that file is run Haskell is not really in the picture any more!

This is therefore more specific than normal function application, because the abstract problem I wrote in JavaScript is,

1. I have a program which computes {a function from (X, Y) pairs to programs which compute Zs}.
2. I also have a program which computes an X, and a program which computes a Y.
3. I want to put these all together into a program which computes a Z.

That's not just function composition itself. But a function can do that.

Peeking inside monads

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.

We also add two other properties, the adjective should be outputtish,

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

and universally embeddable,

pure: 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.

Now this metaprogramming idea obviously contains a monad. In JS we would write,

interface IO<x> {
  run: () => Promise<x>
}
function join<x>(pprog: IO<IO<x>>): IO<x> {
  return { run: () => pprog.run().then(prog => prog.run()) };
}
function map<x, y>(prog: IO<x>, fn: (in: x) => y): IO<y> {
  return { run: () => prog.run().then(x => fn(x)) }
}
function pure<x>(input: x): IO<x> {
  return { run: () => Promise.resolve(input) }
}
// with those you can also define,
function bind<x, y>(prog: IO<x>, fn: (in: x) => IO<y>): IO<y> {
  return join(map(prog, fn));
}

But the fact that a pattern exists does not mean it is useful! I am claiming that these functions turn out to be all you need to resolve the problem above. And it is not hard to see why: you can use bind to create a function scope inside of which the adjective doesn't exist, and manipulate your values there:

function ourGoal<x, y, z>(
  fnProg: IO<(inX: x, inY: y) => IO<z>>,
  xProg: IO<x>,
  yProg: IO<y>): IO<z> {
    return bind(fnProg, fn =>
      bind(xProg, x =>
        bind(yProg, y => fn(x, y))));
}

How this answers your question

Notice that in the above we choose an order of operations by how we write the three binds. We could have written those in some other order. But we needed all the parameters to run the final program.

This choice of how we sequence our operations is indeed realized in the function calls: you are 100% right. But the way that you are doing it, with only function composition, is flawed because it demotes the effects down to side-effects in order to get the types through.

Answer 3

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).