Efficient and/or idiomatic way to turn Seq[Either[String, Int]] to (Seq[String], Seq[Int])

Question

Slightly simplifying, my problem comes from a list of strings input that I want to parse with a function parse returning Either[String,Int].

Then list.map(parse) returns a list of Eithers. The next step in the program is to format an error message summing up all the errors or passing on the list of parsed integers.

Lets call the solution I'm looking for partitionEithers.

Calling

partitionEithers(List(Left("foo"), Right(1), Left("bar")))

Would give

(List("foo", "bar"),List(1))

Finding something like this in the standard library would be best. Failing that some kind of clean, idiomatic and efficient solution would be best. Also some kind of efficient utility function I could just paste into my projects would be ok.

I was very confused between these 3 earlier questions. As far as I can tell, neither of those questions matches my case, but some answers there seem to contain valid answers to this question.

Did you mean "*or* passing on the list of parsed integers", or "*and*"? If it's really *or*, then you need an `Either[Seq[String], Seq[Int]]`, and not a `(Seq[String], Seq[Int])`. — dcastro, Apr 11 '16 at 16:02
@dcastro :D you are right. Thanks! I was even more confused than I suspected. I'm leaving the question here in case someone actually needs what I asked for and since there are already multiple answers. — Peter Lamberg, Apr 11 '16 at 16:50
@PeterLamberg - Incidentally, if you care about speed, your solution was fastest by a sizable margin. — Rex Kerr, Apr 11 '16 at 17:16
@RexKerr Good to know :) I was imagining what this could look like if it was a library function and I appreciate optimized library functions. I also tried to generalize on the collection type based on this [answer by oxbow_lakes](http://stackoverflow.com/a/6491530/1148030), but I wasn't satisfied with the results. — Peter Lamberg, Apr 11 '16 at 19:08
Possible duplicate of [How to split a List\[Either\[A, B\]\]](http://stackoverflow.com/questions/26576530/how-to-split-a-listeithera-b) — Peter Neyens, Apr 27 '16 at 09:02
@PeterNeyens yup, it really seems like my question is a dupe. I wonder why I couldn't find "How to split a List[Either[A, B]]". I think I really tried. Perhaps I failed to use the keyword "split". I'll think about this a bit and close this question soon. — Peter Lamberg, Apr 27 '16 at 18:43
@PeterLamberg I don't know if it needs to be actually closed. There is some interesting information in the comments thanks to Rex Kerr and we got some different answers (like yours) along with some similar (like mine :-) ). I just thought it was a good idea to link the 2 questions. — Peter Neyens, Apr 27 '16 at 19:19

Sascha Kolberg · Answer 1 · 2016-04-11T17:41:16.597

7

Scala collections offer a partition function:

val eithers: List[Either[String, Int]] = List(Left("foo"), Right(1), Left("bar"))

eithers.partition(_.isLeft) match {
  case (leftList, rightList) =>
    (leftList.map(_.left.get), rightList.map(_.right.get))
}

=> res0: (List[String], List[Int]) = (List(foo, bar),List(1))

UPDATE

If you want to wrap it in a (maybe even somewhat type safer) generic function:

def partitionEither[Left : ClassTag, Right : ClassTag](in: List[Either[Left, Right]]): (List[Left], List[Right]) =
  in.partition(_.isLeft) match {
    case (leftList, rightList) =>
      (leftList.collect { case Left(l: Left) => l }, rightList.collect { case Right(r: Right) => r })
}

edited Apr 11 '16 at 17:41

answered Apr 11 '16 at 16:05

Sascha Kolberg

7,092
1
31
37

Simple and elegant and not typesafe. Partition doesn't understand that you're restricting the allowed types. – Rex Kerr Apr 11 '16 at 17:07
@RexKerr I am aware that `partition(_.isLeft)` does know that it partitions into Lefts and Rights. But the result should in real life be exactly that, shouldn't it? I am curious, would it be *typesafe* enough for a pragmatist or is there a scenario where it could actually fail? Also, I updated my answer, would that be more type safe? – Sascha Kolberg Apr 11 '16 at 17:46
1

In your update, the partition is doing exactly zero work. The pair of `collect`s does everything, whether or not you partition in advance! Anyway--yes, it might be okay for a pragmatist, but not for an idealist. – Rex Kerr Apr 12 '16 at 16:45

score 5 · Answer 2 · answered Apr 11 '16 at 18:08

You could use separate from MonadPlus (scalaz) or MonadCombine (cats) :

import scala.util.{Either, Left, Right}

import scalaz.std.list._
import scalaz.std.either._
import scalaz.syntax.monadPlus._

val l: List[Either[String, Int]] = List(Right(1), Left("error"), Right(2))
l.separate  
// (List[String], List[Int]) = (List(error),List(1, 2))

score 4 · Accepted Answer · answered Apr 11 '16 at 16:37

4

I don't really get the amount of contortions of the other answers. So here is a one liner:

scala> val es:List[Either[Int,String]] = 
           List(Left(1),Left(2),Right("A"),Right("B"),Left(3),Right("C"))
es: List[Either[Int,String]] = List(Left(1), Left(2), Right(A), Right(B), Left(3), Right(C))

scala> es.foldRight( (List[Int](), List[String]()) ) { 
         case ( e, (ls, rs) ) => e.fold( l => ( l :: ls, rs), r => ( ls, r :: rs ) ) 
       }
res5: (List[Int], List[String]) = (List(1, 2, 3),List(A, B, C))

answered Apr 11 '16 at 16:37

pedrofurla

12,763
1
38
49

1

This is 3x slower than the OP's collections-internals-like implementation, by the way. – Rex Kerr Apr 11 '16 at 17:11
2

Yes, that's why I said "3x" instead of something vague. – Rex Kerr Apr 12 '16 at 16:43
Anything more sophisticated than subtracting timesptamps from before and after? – pedrofurla Apr 12 '16 at 17:21
I used my rapid benchmarking tool, Thyme (on a list of length 100,000 with approximately equal numbers of left and right cases). – Rex Kerr Apr 14 '16 at 21:59

Peter Lamberg · Answer 4 · 2018-01-14T19:07:37.283

Here is an imperative implementation mimicking the style of Scala collection internals.

I wonder if there should something like this in there, since at least I run into this from time to time.

import collection._
import generic._
def partitionEithers[L, R, E, I, CL, CR]
                    (lrs: I)
                    (implicit evI: I <:< GenTraversableOnce[E],
                              evE: E <:< Either[L, R],
                              cbfl: CanBuildFrom[I, L, CL],
                              cbfr: CanBuildFrom[I, R, CR])
                    : (CL, CR) = {
  val ls = cbfl()
  val rs = cbfr()

  ls.sizeHint(lrs.size)
  rs.sizeHint(lrs.size)

  lrs.foreach { e => evE(e) match {
    case Left(l)  => ls += l
    case Right(r) => rs += r
  } }

  (ls.result(), rs.result())
}

partitionEithers(List(Left("foo"), Right(1), Left("bar"))) == (List("foo", "bar"), List(1))
partitionEithers(Set(Left("foo"), Right(1), Left("bar"), Right(1))) == (Set("foo", "bar"), Set(1))

Thanks @HTNW for the generic collection handling. Impressive! I'm slightly worried that the signature is not very understandable now... perhaps adding some type bounds or tweaking the naming could help? (also adding back the sizeHints) — Peter Lamberg, Jan 14 '18 at 19:06

curious · Answer 5 · 2016-04-11T17:25:14.883

0

You can use foldLeft.

  def f(s: Seq[Either[String, Int]]): (Seq[String], Seq[Int]) = {
    s.foldRight((Seq[String](), Seq[Int]())) { case (c, r) =>
      c match {
        case Left(le) => (le +: r._1, r._2)
        case Right(ri) => (r._1 , ri +: r._2)
      }
    }
  }

val eithers: List[Either[String, Int]] = List(Left("foo"), Right(1), Left("bar"))

scala> f(eithers)
res0: (Seq[String], Seq[Int]) = (List(foo, bar),List(1))

edited Apr 11 '16 at 17:25

answered Apr 11 '16 at 16:11

curious

2,908
15
25

1

This is a disaster used on `List`. `:+` is O(n) in the length of the list, so it's an O(n^2) algorithm. – Rex Kerr Apr 11 '16 at 17:15
@RexKerr: True. I changed it and used a prepend (+:) which is a constant operation. – curious Apr 11 '16 at 17:24

Efficient and/or idiomatic way to turn Seq[Either[String, Int]] to (Seq[String], Seq[Int])

5 Answers5

Linked