2

There is a typeclass called Parallel in Cats. The purpose of this class is to provide parallel computations for some monads that don't support parallel computations out of the box like Either for example.

I know that Monad is used for dependent computations and thus requires sequential execution. Applicative is used for independent computations, so such computations can be parallelized.

It's also known that each Monad is Applicative (monad is applicative functor).

So now I can't put together all concepts from the theory. If all monads are also applicatives, why I can't use applicative nature of monads for parallel computations and I need this Parallel typeclass?

Is it just an option for Applicative to support parallelism or it's a requirement?

Bogdan Vakulenko
  • 3,380
  • 1
  • 10
  • 25
  • 3
    Your understanding is almost correct, but you have a simple error. - _"Applicative is used for independent computations"_. That is not strictly true, an **Applicative** provides a mean to apply a function lifted on an `F` context to an effectual value. From that, you can derive a way to take two effectual values and return an effect of the tuple of the values, and that is it. On the other hand, a **Monad** takes that and adds the constraint of sequentiality, as such it guarantees that when creating the tuple, the first value will be evaluated first and then the second. – Luis Miguel Mejía Suárez Jul 23 '19 at 15:00
  • 2
    From that, one can conclude that an **Applicative** can be used to perform _"parallel"_ operations, whereas a **Monad** can not, because the **Monad** has the restriction to be sequential while the **Applicative** does not _(but it does not guarantee to be in parallel, for example it may also first evaluate the second and then the first, and still be valid)_. - Now, given that all **Monads** are also **Applicatives** means that you can implement all the abstract methods on the last using the ones of the former, but you still have to follow the **Monad** rules. Thus, it will be sequential. – Luis Miguel Mejía Suárez Jul 23 '19 at 15:04
  • @LuisMiguelMejíaSuárez thanks for your explanation. Is it correct to say that `Either` monad implementation automatically provide non-parallel `Applicative`, but nothing stops us from implementing parallel `Applicative` for `Either` if we want? – Bogdan Vakulenko Jul 23 '19 at 15:16
  • @LuisMiguelMejíaSuárez if so, then what are benefits of using `Parallel` typeclass in compare to implementing parallel `Applicative` in addition to `Monad`? – Bogdan Vakulenko Jul 23 '19 at 15:24
  • 2
    _"Well yes, but actually no"_ I am not sure if you can even implement a _"parallel"_ **Applicative** for `Either` _(I believe not, but lets suppose that yes)_. The problem is that, for the coherence, you should only have one instance of each **Typeclass** for each type. As such, you should not have two **Applicatives** for `Either` _(or for any effect)_. Thus, the use of **Parallel**, is to provide a new **Typeclass**, which is not related to neither **Applicative** nor **Monad** to provide those "parallel" operations to those effects that are **Monads** but can have a parallel **Applicative** – Luis Miguel Mejía Suárez Jul 23 '19 at 15:32
  • 2
    But going further, if you check the [scaladoc](https://typelevel.org/cats/api/cats/Parallel.html) of **Parallel**, you will see that it is parametric on two types `M` & `F` _(where `M` has a **Monad** and `F` has an **Applicative**)_ thus, it also covers cases when the **Monad** itself is not capable of doing "parallel" computations, but you can convert it into another effect which does. For example, take a look to the [instances](https://typelevel.org/cats/api/cats/instances/ParallelInstances.html) of **Parallel**, you will see that for `Either` it goes to `Validated`. – Luis Miguel Mejía Suárez Jul 23 '19 at 15:38
  • 2
    Whereas for [**Ior**](https://typelevel.org/cats/api/cats/data/Ior$.html) it uses itself for both, the **Monad** as well as the **Applicative**. - Thus, in this case, it does breaks the coherence principle, by creating a new **Applicative** that is "parallel". You can check that on the source code. – Luis Miguel Mejía Suárez Jul 23 '19 at 15:39
  • Luis that was a great explanation but it should have been an Answer rather than 7 comments :) – Wogan Jul 25 '19 at 23:53
  • 2
    @LuisMiguelMejíaSuárez, Ior does not break the coherence principle. It is indeed accumulating errors on `Ior.Both`, but not on `Ior.Left`. See example here: https://stackoverflow.com/a/60400523/4296401 . `Ior` has its own Parallel Instance that will accumulate errors also on `Ior.Left` with the `par*` combinator family such as `parTraverse`, `parMapN`, etc. – montrivo Mar 02 '20 at 23:10

0 Answers0