Add a Parallel type class

[LukaJCB]

In PureScript there is a Parallel type class, which introduces the idea of a Monad that supports parallel composition with a related Applicative instance. This could work for IO in cats-effect and a theoretical ParIO, but also for Either and Validated.
We could also include instances for Kleisli (ReaderT) and WriterT.

I think it could really be useful, especially with regards to parTraverse.

[johnynek]

This seems really cool. So, something like this:

trait Parallel[M[_], F[_]] {
  def applicative: Applicative[F]
  def monad: Monad[M]
  def parallel: FunctionK[M, F]
  def sequential: FunctionK[F, M]
}

or maybe:

case class Parallel[M[_], A](toMonad: M[A])

trait HasParallel[M[_], F[_]] {
  def applicative: Applicative[F]
  def monad: Monad[M]
  def parallel: FunctionK[M, F]
  def sequential: FunctionK[F, M]
}

object Parallel {
  implicit def applicative[M[_], F[_]](implicit hp: HasParallel[M, F]): Applicative[Parallel[M, ?]] = ..
}

anyway... however we encode, this is a great idea. Often we have two paths for Applicative vs Monad (List, Either, Future come to mind).

[LukaJCB]

Something quick and dirty I came up with:

trait Parallel[F[_], M[_]] {
  def sequential(implicit m: Monad[M], f: Applicative[F]): F ~> M
  def parallel(implicit m: Monad[M], f: Applicative[F]): M ~> F
}

object Parallel {
  def parSequence[M[_]: Monad, F[_]: Applicative, T[_]: Traverse, A]
    (tma: T[M[A]])(implicit P: Parallel[F, M]): M[T[A]] = {
    val fta: F[T[A]] = implicitly[Traverse[T]].traverse(tma)(P.parallel.apply)
    P.sequential.apply(fta)
  }
}

implicit def parEitherValidated[E: Semigroup] = new Parallel[Validated[E, ?], Either[E, ?]] {
  def sequential(implicit m: Monad[Either[E, ?]], f: Applicative[Validated[E, ?]]): Validated[E, ?] ~> Either[E, ?] =
    λ[Validated[E, ?] ~> Either[E, ?]](_.toEither)
  def parallel(implicit m: Monad[Either[E, ?]], f: Applicative[Validated[E, ?]]): Either[E, ?] ~> Validated[E, ?] =
    λ[Either[E, ?] ~> Validated[E, ?]](_.toValidated)
}

val list: List[Either[String, Int]] = List(Right(42), Left("Damn "), Left("Oops"))
val ex: Either[String, List[Int]] = Parallel.parSequence[Either[String, ?], Validated[String, ?], List, Int](list)

Doesn't quite work without the type annotations on parSequence yet due to some ambiguous implicits that I didn't have time to look into yet, but it already does what it should:

scala> Test.ex
res1: Either[String,List[Int]] = Left(Damn Oops)

[LukaJCB]

I now realize why the above can't work, here's a revised version that works with type inference based on johnynek's idea:

trait Parallel[M[_], F[_]] {
  def applicative: Applicative[F]
  def sequential(implicit M: Monad[M]): F ~> M
  def parallel(implicit M: Monad[M]): M ~> F
}

object Parallel {
  def parSequence[T[_]: Traverse, M[_]: Monad, F[_], A]
      (tma: T[M[A]])(implicit P: Parallel[M, F]): M[T[A]] = {
    val fta: F[T[A]] = Traverse[T].traverse(tma)(P.parallel.apply)(P.applicative)
    P.sequential.apply(fta)
  }
}

implicit def parEitherValidated[E: Semigroup] = new Parallel[Either[E, ?], Validated[E, ?]] {
  def applicative: Applicative[Validated[E, ?]] = Validated.catsDataInstancesForValidated

  def sequential(implicit M: Monad[Either[E, ?]]): Validated[E, ?] ~> Either[E, ?] =
    λ[Validated[E, ?] ~> Either[E, ?]](_.toEither)

  def parallel(implicit M: Monad[Either[E, ?]]): Either[E, ?] ~> Validated[E, ?] =
    λ[Either[E, ?] ~> Validated[E, ?]](_.toValidated)
}

val list: List[Either[String, Int]] = List(Right(42), Left("Damn "), Left("Oops"))
val ex: Either[String, List[Int]] = Parallel.parSequence(list)

Bonus: a parallel map2:

def parMap2[M[_]: Monad, F[_], A, B, C](ma: M[A], mb: M[B])(f: (A, B) => C)(implicit P: Parallel[M, F]): M[C] = {
  implicit val F = P.applicative
  val fc = Applicative[F].map2(P.parallel.apply(ma), P.parallel.apply(mb))(f)

  P.sequential.apply(fc)
}

It would probably be possible to define a parMapN method on tuples through syntax enhancement, that could make use of this type class. Might make sense to talk about something like that later though.