Best way to turn a Lists of Eithers into an Either of Lists?

I have some code like the below, where I have a list of Eithers, and I want to turn it into an Either of Lists ... in particular (in this case), if there are any Lefts in the list, then I return a Left of the list of them, otherwise I return a Right of the list of the rights.

val maybe: List[Either[String, Int]] = getMaybe
val (strings, ints) = maybe.partition(_.isLeft)
strings.map(_.left.get) match {
  case Nil => Right(ints.map(_.right.get))
  case stringList => Left(stringList)
}

Calling get always makes me feel like I must be missing something.

Is there a mor开发者_运维知识库e idiomatic way to do this?

data.partition(_.isLeft) match {                            
  case (Nil,  ints) => Right(for(Right(i) <- ints) yield i)        
  case (strings, _) => Left(for(Left(s) <- strings) yield s)
}

For one pass:

data.partition(_.isLeft) match {                            
  case (Nil,  ints) => Right(for(Right(i) <- ints.view) yield i)        
  case (strings, _) => Left(for(Left(s) <- strings.view) yield s)
}

Starting in Scala 2.13, most collections are now provided with a partitionMap method which partitions elements based on a function returning either Right or Left.

In our case, we don't even need a function that transforms our input into Right or Left to define the partitioning since we already have Rights and Lefts. Thus a simple use of identity!

Then it's just a matter of matching the resulting partitioned tuple of lefts and rights based on whether or not there are any lefts:

eithers.partitionMap(identity) match {
  case (Nil, rights) => Right(rights)
  case (lefts, _)    => Left(lefts)
}
// * List[Either[String, Int]] = List(Right(3), Left("error x"), Right(7))
//         => Either[List[String],List[Int]] = Left(List(error x))
// * List[Either[String, Int]] = List(Right(3), Right(7))
//         => Either[List[String],List[Int]] = Right(List(3, 7))

For the understanding of partitionMap here is the result of the intermediate step:

List(Right(3), Left("error x"), Right(7)).partitionMap(identity)
// (List[String], List[Int]) = (List(error x), List(3, 7))

Solution from Functional Programming in Scala book.

def sequence[E,A](es: List[Either[E,A]]): Either[E,List[A]] = 
    traverse(es)(x => x)

def traverse[E,A,B](es: List[A])(f: A => Either[E, B]): Either[E, List[B]] = 
    es match {
      case Nil => Right(Nil)
      case h::t => (f(h) map2 traverse(t)(f))(_ :: _)
    }
def map2[EE >: E, B, C](a: Either[E, A], b: Either[EE, B])(f: (A, B) => C): 
   Either[EE, C] = for { a1 <- a; b1 <- b } yield f(a1,b1)

val list = List(Left("x"),Right(2), Right(4))
val strings = for (Left(x) <- list) yield(x)
val result = if (strings.isEmpty) Right(for (Right(x) <- list) yield(x)) 
             else Left(strings)

You can write a generalized version of split as follows:

def split[X, CC[X] <: Traversable[X], A, B](l : CC[Either[A, B]])
   (implicit bfa : CanBuildFrom[Nothing, A, CC[A]], bfb : CanBuildFrom[Nothing, B, CC[B]]) : (CC[A], CC[B]) = {
  def as = {
    val bf = bfa()
    bf ++= (l collect { case Left(x) => x})
    bf.result
  }

  def bs = {
    val bf = bfb()
    bf ++= (l collect { case Right(x) => x})
    bf.result
  }

  (as, bs)
}

Such that:

scala> List(Left("x"),Right(2), Right(4)) : List[Either[java.lang.String,Int]]
res11: List[Either[java.lang.String,Int]] = List(Left(x), Right(2), Right(4))

scala> split(res11)
res12: (List[java.lang.String], List[Int]) = (List(x),List(2, 4))

scala> Set(Left("x"),Right(2), Right(4)) : Set[Either[java.lang.String,Int]]
res13: Set[Either[java.lang.String,Int]] = Set(Left(x), Right(2), Right(4))

scala> split(res13)
res14: (Set[java.lang.String], Set[Int]) = (Set(x),Set(2, 4))

I kind of don't want any karma for this as it's a merge of Chris's answer and Viktor's from here.. but here's an alternative:

def split[CC[X] <: Traversable[X], A, B](xs: CC[Either[A, B]])
   (implicit bfa: CanBuildFrom[Nothing, A, CC[A]], bfb: CanBuildFrom[Nothing, B, CC[B]]) : (CC[A], CC[B]) =
  xs.foldLeft((bfa(), bfb())) {
    case ((as, bs), l@Left(a)) => (as += a, bs)
    case ((as, bs), r@Right(b)) => (as, bs += b)
  } match {
    case (as, bs) => (as.result(), bs.result())
  }

Example:

scala> val eithers: List[Either[String, Int]] = List(Left("Hi"), Right(1))
eithers: List[Either[String,Int]] = List(Left(Hi), Right(1))

scala> split(eithers)
res0: (List[String], List[Int]) = (List(Hi),List(1))

If you want to have something more general and also functional then Validated from cats library is the type you might want. It is something like Either that can aggregate Errors. And in combination with NonEmptyList it can be really powerful.

http://typelevel.org/cats/datatypes/validated.html

Isn't a more elegant way?

  def flatten[E,A](es: List[Either[E,A]]): Either[E,List[A]] = {
    @tailrec
    def go(tail: List[Either[E,A]], acc: List[A]): Either[E,List[A]] = tail match {
      case Nil  => Right(acc)
      case h::t => h match {
        case Left(e)  => Left(e)
        case Right(a) => go(t, a :: acc)
      }
    }
    go(es, Nil) map { _ reverse }
  }

• tail recursion
• one pass, assuming the a :: acc is a bullet-fast
• but still, reverse in the end
• partitionMap, is probably faster, because of internal implementation based on builder
• but this one is the lasy. You will get Left immediately.

To extract Lefts and Rights separately:

val data: List[Either[String, Int]] = List(
  Right(1), 
  Left("Error #1"), 
  Right(42), 
  Left("Error #2")
)


val numbers: List[Int] = data.collect { case Right(value) => value }
val errors: List[String] = data.collect { case Left(error) => error }


println(numbers) // List(1, 42)
println(errors)  // List(Error #1, Error #2)