Applicative functions like map2, product, etc are defined in terms of flatMap

[txsmith]

in FlatMap, you'll find the following implementation for various functions:

@typeclass trait FlatMap[F[_]] extends Apply[F] {
  ...
  override def ap[A, B](ff: F[A => B])(fa: F[A]): F[B] =
    flatMap(ff)(f => map(fa)(f))

  override def product[A, B](fa: F[A], fb: F[B]): F[(A, B)] =
    flatMap(fa)(a => map(fb)(b => (a, b)))

  override def ap2[A, B, Z](ff: F[(A, B) => Z])(fa: F[A], fb: F[B]): F[Z] =
    flatMap(fa)(a => flatMap(fb)(b => map(ff)(_(a, b))))

  override def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z] =
    flatMap(fa)(a => map(fb)(b => f(a, b)))

  override def productR[A, B](fa: F[A])(fb: F[B]): F[B] =
    flatMap(fa)(_ => fb)

  override def productL[A, B](fa: F[A])(fb: F[B]): F[A] =
    map2(fa, fb)((a, _) => a)

This makes it such that whenever I define a Monad that has a parallel implementation of ap, none of the other functions will have the parallel behaviour!

Is there a reason these methods are defined in terms of flatMap and not in terms of ap? For example, I would expect map2 to be implemented as:

override def map2[A, B, Z](fa: F[A], fb: F[B])(f: (A, B) => Z): F[Z] =
  fa.map(a => f.curried.apply(a)).ap(fb)

so that it automatically inherits parallel behaviour of ap

[djspiewak]

This makes it such that whenever I define a Monad that has a parallel implementation of ap, none of the other functions will have the parallel behaviour!

This is why you don't want to do something like this. :-D

The relationship between ap and flatMap such that ap(ff)(fa) <-> flatMap(ff)(f => map(fa)(f)) is actually by law; this is what Monad is defined to be. So if you're defining an ap which is magically parallel on an F[_] which forms a Monad, then you're violating that law, which will cause downstream code to break in very subtle ways.

Fortunately, this is a relatively common issue, which is why the Parallel typeclass was defined. The idea behind Parallel is you can establish a relationship between F and F' such that F <~> F' where F forms a Monad and F' forms an Applicative which has semantics inconsistent with Monad[F]. The classic example of this is parallelism (e.g. in the IO monad), but it also applies in other areas, such as the relationship between Either and ValidatedNel.

[txsmith]

Thanks for the detailed info! That's interesting, I was not aware that this is an actual Monad law, but intuitively I can imagine this to be a desirable property. Out of curiosity, are there any known/documented cases where violation of this law has caused problems? I'm not sure I see an immediate and concrete problem given our use-case, especially since flatMap is still sequential and it would pass all other monad laws (identity and assoc). The Parallel class certainly seems interesting, i'll take a look!

[johnynek]

but @djspiewak I think this explanation misses something: equivalence does not mean it is equally efficient. I really don't see why anyone bothered to override these in FlatMap. They are already defined in Apply and it can be a deoptimization.

I had to override these methods in Parser cases, because, yes it is equivalent, but flatMap is expensive compared to product: you can skip calling a function, which can be significant in a tight loop.

I agree this is an issue, and I think the defaults should prefer product/ap when possible, over flatMap, since, as you point out, the result shouldn't change (but the runtime might).

[djspiewak]

Out of curiosity, are there any known/documented cases where violation of this law has caused problems?

Yes! Future is the canonical example, since it is relatively easy to implement ap against Future such that it is inconsistent with flatMap and magically parallel. However, this results in downstream surprises and unexpected performance characteristic shifts in the face of refactorings which would rationally be expected to be identity (e.g. *> vs >>).

but @djspiewak I think this explanation misses something: equivalence does not mean it is equally efficient

Conversely, you don't actually know what is or is not efficient in this layer. For example, on IO, the flatMap-based overrides are faster than the originals. I would imagine that something like this was the motivation for adding these overrides in the first place, though I don't know for sure.

We generally have to consider evaluation to be instantaneous for most purposes, otherwise laws in general break down. I mean, you literally lose the functor identity if you don't ignore this case. Anything which does care about efficiency is going to need to implement overrides at a more concrete level where they know what is right or wrong, as you did with Parser.

I agree this is an issue, and I think the defaults should prefer product/ap when possible, over flatMap, since, as you point out, the result shouldn't change (but the runtime might).

Just going to the specific point of the OP… Parallelism is not an oblivious concern of the runtime. Future is a great example of where this trips people up in practice (consider the issue with the batching executor in 2.13), but even without delving into impure monads, it's easy to hit problems. IO[A] is pure, but it's evaluation may not be, and automagically making *> parallel while keeping >> sequential would be devastating and immediately break tons of programs. Even if we restrict things further, and imagine a totally pure use of IO such that no side-effects are executed during evaluation, we still likely want to be very strict about parallel vs sequential evaluation due to the need to control units of granularity and cache affinity. In other words, it's not just a runtime concern: it deals with the nature of the program you are describing.

I don't have any strong objections to removing the override, but this is a subtle issue and it isn't entirely black and white.

[johnynek]

I hear you Daniel, but if we reread the original question: he is saying he has a Monad that does have a parallel ap, but the way FlatMap has defaulted it has gone out of its way to destroy that parallelism.

If we were to minimize code, we would not have added these implementations, since by law, they are equivalent. So, we have already expended effort and added code under the belief that on balance it is a win. I don't see what that argument could be that it is a win.

I hear you that IO may not optimize product or ap (I think it easily could, and may benefit traverse, for instance), but surely cats-effect is not the reason for that choice, is it?

By overriding all these in terms of flatMap, every subclass of Monad/FlatMap now has to go through and re-override them, and unfortunately, the laws don't even check all those functions (I noticed when changing some recently and noticing they were not covered by coverage checks).

[djspiewak]

he is saying he has a Monad that does have a parallel ap, but the way FlatMap has defaulted it has gone out of its way to destroy that parallelism

And what I'm saying is that monad is already broken and will cause other problems inevitably as people attempt to use it. Just as Future does if you don't carefully implement its ap in terms of its flatMap. Giving ap and flatMap divergent runtime semantics (such that these implementations are not at the very least substitutable absent performance questions) is kind of like giving + and * divergent runtime semantics on integers, and should be considered bad practice at best.

If we were to minimize code, we would not have added these implementations, since by law, they are equivalent. So, we have already expended effort and added code under the belief that on balance it is a win. I don't see what that argument could be that it is a win.

This, I agree with. I don't see a compelling overriding benefit to these overrides, and I'm of the opinion that code must justify its existence rather than justifying its removal. With that said, I want to look at it a little more closely to make sure I'm not missing anything.

I hear you that IO may not optimize product or ap (I think it easily could, and may benefit traverse, for instance), but surely cats-effect is not the reason for that choice, is it?

It actually could be, I haven't looked at the git blame.

To your point about optimization though… this is a subtle art. Remember that IO is asynchronous, meaning that callbacks are already in the evaluation chain unavoidably (intuitively, we don't know whether the left side is async). This means that, while IO could provide a specific implementation of product which is very slightly faster in the straight line case, it would only be faster because it avoids the allocation of the Function1. Everything else that happens in the flatMap call chain would happen in the product case. Additionally, implementing a special variant would miss out on several optimizations which are applied to map and flatMap with respect to errors. These optimizations could be reapplied to product, but now you're hitting diminishing returns on effort.

As for ap, I was being serious when I said that a primitive version of ap (as opposed to overriding the built-in in terms of flatMap) is almost certainly slower with IO.

The real problem that IO would run into is the fact that we can only have a certain number of primitive cases before the entire runloop deoptimizes itself due to having too many branches in the match. I forget exactly where that cutoff is, but off the top of my head, I think we're only about 2-3 cases away from that. Spending one of those remaining cases on something that is, at best, a tiny gain outside the hot path is not really worth it.

However, overriding the default implementation of product to use flatMap more directly is a significant win and doesn't run afoul of any of these issues.

It's tough to generalize the performance implications of these things because there are so many different possible implementation types for various types of monads. I do think that's an argument more in favor of removing the overrides, but my point still stands that you can't universally look at this from a performance standpoint and make general claims.

[johnynek]

Daniel,

look man... you are too fixated on IO.

And what I'm saying is that monad is already broken and will cause other problems inevitably as people attempt to use it. Just as Future does if you don't carefully implement its ap in terms of its flatMap. Giving ap and flatMap divergent runtime semantics (such that these implementations are not at the very least substitutable absent performance questions) is kind of like giving + and * divergent runtime semantics on integers, and should be considered bad practice at best.

1. you can have perfectly lawful Monads where product is not implemented by flatMap, yet given equivalent values despite non-equivalent runtime. (e.g. Parser, Gen, Function0, Function1, etc...)
2. no one is saying to make them have different values that I can see. Please stop arguing against that since no one is proposing that in this particular thread.
3. You can still have a future-like monad that does not fail (e.g. for being explicit about modeling parallel computation) where like above you can have the result values be equivalent yet the product be parallel while flatMap is clearly not (consider the kind of parallelism in parallel collections libraries which is not about tasks that can fail, but just about which tasks run concurrently for optimal use of CPU resources).

Please let me know if you feel I am not understanding you. I feel like I have understood your points, but maybe I am wrong. I feel like you have not understood my points above and are speaking at a fairly neophyte level (which I am trying to not take offense to). Yes, we know about laws. Yes laws are good. Yes these functions should be lawful. Yet the original poster, and I, have both hit issues where the typeclass itself is taking the stand that funneling everything through flatMap for some reason is a good idea. And I think we are both saying, that so long as the laws are passed we should write things in the weakest, not the most powerful way.