Can I represent non-sequential/parallel execution with Monads?

Question

So I've finally understood why Applicatives are very useful to represent parallel execution, while Monads very useful to represent sequential execution.

That being said, I've also understood that Monads are more powerful than Applicatives, so can I represent the ap function in terms of the bind function?

In other words... can I represent parallel execution with Monads?

Answer 1

The Monad laws have something to say about this:

Furthermore, the Monad and Applicative operations should relate as follows:

pure = return
(<*>) = ap

Given that ap is defined to compose computations sequentially,

ap mf mx = do
    f <- mf
    x <- mx
    return (f x)

there's only one way to read that law: a type which exposes a monadic interface cannot use Applicative to do parallel computation. You could provide a newtype wrapper for your monad which has a parallel Applicative instance and no Monad instance, but you can't do both at the same time.

---

In theory, theory and practice are the same, but in practice, they are not. In the real world you do in fact see people bending these rules and interpreting the above law to mean that (<*>) should be morally equivalent to ap, even if it's not exactly equivalent.

The best example of this that I know happens to be the one which directly addresses your question. Haxl is a library implementing a domain-specific language for concurrent IO. The GenHaxl monad's <*> automatically parallelises two computations where possible, whereas its >>= runs them in sequence (because it has to). This clearly goes against the letter of the law, but since Haxl is meant to be used for database reads which don't mutate anything (rather than writes, which do) you can kinda get away with it and the world doesn't explode.