How to transform F[Either[A, B]] to Either[F[A], F[B]]

A little bit of background: There is a .separate function in cats that allows me to get tuple (F[A], F[B]) out of F[Either[A, B]]. Given that, one can easily construct Either[F[A], F[B]] - given we can check F for emptiness (a monoid would do?). The code for list could look like this

val l: List[Either[_, _]] = ???
l.separate match {
  case (Nil, rights) => Right(rights)
  case (lefts, _) => Left(lefts)
}

But this seems like a more general concept but I am not quite sure what that is. It looks kinda similar to .sequence but our G has two holes. That is, we want a transformation F[G[A, B]] -> G[F[A], F[B]].

Do you happen to know if such concept exists or how to achieve this goal with cats without pattern matching / if statements / Either.cond?

Solution

You might try it with a combination of Alternative and Traverse.

This special case can be generalized from List to an arbitrary F:

def collectErrors[A, B](xs: List[Either[A, B]]): Either[List[A], List[B]] = {
  xs.traverse(_.left.map(List(_)).toValidated).toEither
}

Here is a shopping list of stuff that we need to make it work:

We need some kind of replacement for List(_). That's usually Applicative[F].pure(_) (or _.pure[F]), so we need Applicative.
We need a Monoid on F[X] so we can accumulate errors in the left part of Validated. Fortunately, there is MonoidK[F[_]], which knows how to generate a Monoid[F[X]] for any given X
The F[_] must be traversable so we can get from F[Validated[F[A], B]] to Validated[F[A], F[B]], thus we need Traverse.

There is a trait Alternative, which is a combination of Applicative and MonoidK. Putting it all together gives you:

  import scala.util.Either
  import cats._
  import cats.syntax.either._
  import cats.syntax.traverse._
  import cats.syntax.applicative._

  def collectErrors[F[_]: Alternative : Traverse, X, Y](xs: F[Either[X, Y]])
  : Either[F[X], F[Y]] = {
    implicit val mon = MonoidK[F].algebra[X]
    xs.traverse(_.left.map(_.pure[F]).toValidated).toEither
  }

This should now work for List, Vector, Chain, etc.