Reducing Iterable[Either[A,B]] to Either[A, Iterable[B]]

Question

I need to reduce an Iterable[Either[Throwable, String]] to an Either[Throwable, Iterable[String]]. I don't know if this operation is pretty common or not, haven't found nothing on the Iterable trait. So I have written this function:

def reduce[A, B](xs: Iterable[Either[A, B]]): Either[A, Iterable[B]] = 
  xs.collectFirst {
    case Left(x) => x
  } match {
    case Some(x) => Left(x)
    case None => Right(xs.collect{case Right(y)=> y})
  }

Can anyone help me to find a better way if this one it isn't?

Answer 1

This operation is often called sequencing, and is available in the standard libraries of some functional languages (such as Haskell). In Scala you can either implement your own, or use an external library like Scalaz. Suppose we have the following, for example:

val xs: List[Either[String, Int]] = List(Right(1), Right(2))
val ys: List[Either[String, Int]] = List(Right(1), Left("1st!"), Left("2nd!"))

Now we can write (using Scalaz 7):

scala> import scalaz._, Scalaz._
import scalaz._
import Scalaz._

scala> xs.sequenceU
res0: Either[String,List[Int]] = Right(List(1, 2))

scala> ys.sequenceU
res1: Either[String,List[Int]] = Left(1st!)

As desired.

---

As a side note, this operation just requires that the outside container be traversable and that the inside container be an applicative functor. Scalaz also provides a ValidationNEL class that's a lot like Either and also fits these requirements, but using sequence on a list of ValidationNELs collects multiple errors instead of stopping at the first:

val zs: List[ValidationNEL[String, Int]] =
  List(1.successNel, "1st".failNel, "2nd".failNel)

Now we get:

scala> print(zs.sequenceU)
Failure(NonEmptyList(1st, 2nd))

You could also use sequence on a list of Options, Promises, etc.

Answer 2

If you don't like the explicit return and want to eliminate the pattern matching while shortening the code somewhat, here is another version:

def reduce[A, B](xs: Iterable[Either[A, B]]): Either[A, Iterable[B]] =
  xs collectFirst {
    case Left(x) => Left(x)
  } getOrElse Right(xs.flatMap(_.right.toOption))

Answer 3

I always find return statements a bit awkward, but this following works:

def reduce[A, B](xs: Iterable[Either[A, B]]): Either[A, Iterable[B]] =
  Right(xs.collect {
    case Left(x) => return Left(x)
    case Right(x) => x
  })