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

Question

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 more idiomatic way to do this?

I find the described problem a bit wierd. The preference of the Strings over the Ints seems a bit asymetric. How about writing something like unzipEither, that returns both a list of strings and a list of ints. This way the method doesn't lose information, which your version does in case of a mixed list. — ziggystar, Jun 27 '11 at 08:25
Sounds like you would maybe be better off using a structure like [Scalaz Validation](http://www.scala-lang.org/node/5465). — Jean-Philippe Pellet, Jun 27 '11 at 09:33

score 28 · Accepted Answer · edited Apr 12 '17 at 07:06

28

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)
}

edited Apr 12 '17 at 07:06

Matthias Braun

32,039
22
142
171

answered Jun 27 '11 at 09:27

Viktor Klang

26,479
7
51
68

Hmm, that is arguably more clear. This seems to do more work, though. It's a pity you can't do this in a single pass. – Eric Bowman - abstracto - Jun 27 '11 at 10:30
You can do it in one pass if you use views instead of List for the resulting type, see my edit. – Viktor Klang Jun 27 '11 at 10:44
1

I think I have to give the .view trick the prize -- thx Viktor. – Eric Bowman - abstracto - Jun 27 '11 at 20:24
Can you explain why you think it should? – Viktor Klang Dec 14 '12 at 12:39

Xavier Guihot · Answer 2 · 2020-10-10T05:33:36.080

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))

score 11 · Answer 3 · answered Apr 25 '15 at 13:17

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)

`traverse` can be written using `foldRight` as well – Valy Dia Jan 14 '19 at 14:20 — Valy Dia, Jan 14 '19 at 14:20

score 6 · Answer 4 · answered Jun 27 '11 at 07:49

6

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)

answered Jun 27 '11 at 07:49

Landei

54,104
13
100
195

score 4 · Answer 5 · answered Jun 27 '11 at 10:30

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))

Out of curiosity, why not create `as` and `bs` as vals? – Kipton Barros Jun 27 '11 at 20:44 — Kipton Barros, Jun 27 '11 at 20:44

score 3 · Answer 6 · edited May 23 '17 at 10:31

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))

score 2 · Answer 7 · answered Feb 06 '17 at 13:58

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

Alexey Rykhalskiy · Answer 8 · 2020-02-25T18:37:44.667

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.

score 0 · Answer 9 · answered Jun 12 '20 at 15:07

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)

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

9 Answers9

Linked