3

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?

ryachza
  • 4,460
  • 18
  • 28
caeus
  • 3,084
  • 1
  • 22
  • 36
  • Read [this answer](https://stackoverflow.com/a/17673690/1048572) on what "more powerful" means and what it doesn't. – Bergi Oct 17 '17 at 12:20
  • 1
    "*can I represent the ap function in terms of the bind function?*" - Yes. Every monad is an applicative (you might need `of` + `bind`). "*can I represent parallel execution with Monads?*" Maybe, but unlikely. Not every applicative is a monad. "*In other words...*" - Nope, those are two very different questions. – Bergi Oct 17 '17 at 12:22
  • _"Every monad is an applicative"_ & _"Applicatives are useful to represent parallel execution" = _"I can represent execution with Monads"_... right? – caeus Oct 17 '17 at 12:31
  • No. Your representation of parallel execution (which you haven't posted unfortunately) may fulfill the applicative laws, but the monad laws might not hold for it. If it's not a monad in the first place, it doesn't help that every monad is an applicative. – Bergi Oct 17 '17 at 12:38
  • If I have two monadic values `mf: m(a->b)` and `ma: m a`, and the combine them with `ap`, I would assume that it represents two parallel computations that are eventually combined. Unlike `bind`,that takes a monadic value and a function returning a monadic value, effectively representing sequential execution. But if `ap` is represented using `bind` the power of parallelization is lost. – caeus Oct 27 '17 at 08:51
  • Just like it happens with Monix `Task`s (unlike scala `Future`s), if I don't use gather or something to explicitly parallelise, they will execute sequentially. So I'm starting to think that the real power of `ap` cannot be expressed with `bind` – caeus Oct 27 '17 at 08:53
  • 1
    I'm starting to think that you are just looking for something with a similar type to `ap` that does something entirely different :-) Yes, parallelism usually would be explicit, unless its seen purely as an implementation optimisation that is not reasoned about. – Bergi Oct 27 '17 at 09:19

3 Answers3

2

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.

Benjamin Hodgson
  • 42,952
  • 15
  • 108
  • 157
  • 1
    Wait! ap and <*> are diferent? – caeus Oct 17 '17 at 16:45
  • Usually, no. In Haxl's case, yes, but they're bending the rules. – Benjamin Hodgson Oct 17 '17 at 16:46
  • My understanding is that the equalities in laws are usually interpreted as **extensional** equalities. And so if `<*>` always returns the same the same results as `ap`, then it doesn't matter if it's implemented differently. And in particular if it's able to use parallel execution and always get the same result as it would from sequential executing (which isn't possible for all monads), then that would be allowed. Is that not correct? – Ben Oct 17 '17 at 23:02
  • 1
    @Ben `<*>` is a pure function whose return value is a _computation_ `m a`. A computation which runs in parallel is different to a computation that runs sequentially, even if the `a` it returns ends up being the same. If you can catch two computations behaving differently, eg by using a database profiler to see queries happening in parallel, they must be different computations! `forkIO foo` is a different computation than `foo`, and you should be suspicious of any formulation of algebraic laws which ask you to consider them the same! – Benjamin Hodgson Oct 17 '17 at 23:08
  • That said, I do agree that your point does apply to eg `parSeq`, which takes a pure computation and parallelises it. There’s no way to observe a computation written with `parSeq` _behaving_ differently to one written without. (It might compute a value faster, but it always returns the same value.) – Benjamin Hodgson Oct 17 '17 at 23:12
  • That's the point I'm making. There are plenty of types for which `x <*> y` and `m ``ap`` y` produce the same value, and you'd never be able to tell if `<*>` used `parSeq` internally. So the sequential bind-based code for `ap` plus the requirement that `(<*>) = ap` don't add up to a general conclusion that `<*>` must be sequential for all monads. For some **particular** monads where the difference would be observable, it *is* a requirement, but that's not what your answer says. – Ben Oct 18 '17 at 00:39
  • And "`m a` is a computation" is just an interpretation, and I don't think that you can validly infer that an `m a` that's produced sequentially is different from one that was produced in parallel, for all monads. Monad/Applicative includes things like `Maybe`, so your `m a` "computation" could be `Just 7`. Is a `Just 7` I produced by evaluating `Just (+1)` and `Just 6` in parallel and then combining them different from one I produced by first evaluating the `Just (+1)` and then the `Just 6` and then combining them? "Monads are computations" isn't any more accurate than "monads are containers". – Ben Oct 18 '17 at 00:43
  • I think we’re talking past each other. I agree with you that `<*>` can be implemented lawfully using `parSeq` even though `ap` doesn't use it. One should draw a distinction between the evaluation strategy used to produce a value and the computational process that is denoted by that value; the former is not observable directly, whereas the latter is. The sense in which Haxl bends the rules is that `f <*> x` denotes a _different effect_ than `ap f x`. Namely, `f <*> x` denotes a process which performs concurrent IO, but `ap f x` denotes a process performing sequential IO. – Benjamin Hodgson Oct 18 '17 at 00:53
0

You can implement <*>, and therefore also ap, from Functor and Monad:

class Functor m => Monad m where
  join :: m (m a) -> m a
  return :: a -> m a

(>>=) :: Monad m => m a -> (a -> m b) -> m b
m >>= f = join $ fmap f m

(<*>) :: Monad m => m (a -> b) -> m a -> m b
fs <*> xs = fs >>= \f -> xs >>= \x -> return (f x)

ap :: Monad m => m (a -> b) -> m a -> m b
ap = (<*>)

This examples hides Haskell's standard Monad definition, and instead defines Monad in terms of join and return, but you can also define join from (>>=); both ways work.

Mark Seemann
  • 225,310
  • 48
  • 427
  • 736
  • Would it actually be executed in parallel? – caeus Oct 17 '17 at 12:25
  • 1
    @caeus That would depend on the type, but as _Bergi_ wrote, while all monads are applicative, not all applicatives are monads. – Mark Seemann Oct 17 '17 at 12:27
  • 1
    [The `Monad` laws](https://hackage.haskell.org/package/base-4.10.0.0/docs/Control-Monad.html#t:Monad) say that `<*>` should be the same as `ap`, so _technically_ a type with a monadic interface shouldn't override `<*>` to do parallel computation. In practice you see people bending the rules (eg [Haxl](https://github.com/facebook/Haxl)) by defining a `<*>` which is _morally_ equivalent to `ap`, even though it may actually behave slightly differently. (In Haxl's case, `<*>` runs computations in parallel whereas `ap` runs them sequentially.) – Benjamin Hodgson Oct 17 '17 at 16:16
  • I decided to write that out as an [answer](https://stackoverflow.com/a/46795027/1523776). – Benjamin Hodgson Oct 17 '17 at 16:37
0

Consider a case: Lets say we have two futures.

val future1 = Future {
  //some long running computation
  1
}

val future2 = Future {
 // some othe long running computation
 2
}

future1.flatMap(_ => future2)

In the above case, future1 and future2 run parallelly provided enough threads are there in the execution pool.

We are able to run the futures parallelly. So, what does this mean?

Monads come into picture when there is data dependence between previous and current tasks (monads). But, if there is no data dependence when they can be run parallelly (at least in case of futures).

Now consider a case:

val future1 = Future {
 // long running task
 1
}

def compute(value: Int) = Future { value + 1}

future1.flatMap(value => compute(value))

Now one future runs after the completion of others. Now execution has to be serial because of data dependency. Second future depends on the value of first future.

Nagarjuna Pamu
  • 14,737
  • 3
  • 22
  • 40