How to reduce Seq[Either[A,B]] to Either[A,Seq[B]]?

Question

Given a sequence of eithers Seq[Either[String,A]] with Left being an error message. I want to obtain an Either[String,Seq[A]] where I get a Right (which will be a Seq[A]), if all elements of the sequence are Right. If there is at least one Left (an error message), I'd like to obtain the first error message or a concatenation of all error messages.

Of course you can post cats or scalaz code but I'm also interested in code not using it.

Edit

I've changed the title, which originally asked for an Either[Seq[A],Seq[B]] to reflect the body of the message.

Hijacker

Answer 1

Edit: I missed that the title of your question asked for Either[Seq[A],Seq[B]], but I did read "I'd like to obtain the first error message or a concatenation of all error messages", and this would give you the former:

def sequence[A, B](s: Seq[Either[A, B]]): Either[A, Seq[B]] =
  s.foldRight(Right(Nil): Either[A, List[B]]) {
    (e, acc) => for (xs <- acc.right; x <- e.right) yield x :: xs
  }

scala> sequence(List(Right(1), Right(2), Right(3)))
res2: Either[Nothing,Seq[Int]] = Right(List(1, 2, 3))

scala> sequence(List(Right(1), Left("error"), Right(3)))
res3: Either[java.lang.String,Seq[Int]] = Left(error)

---

Using Scalaz:

val xs: List[Either[String, Int]] = List(Right(1), Right(2), Right(3))

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

Kristofer

That's shorter than my solution, which uses matching. I think you could use a for-comprehension to make the fold funciton more readable. – Hijacker

Yes, you could replace the body of the function in the foldLeft with: for (xs <- acc.right; x <- e.right) yield x :: xs – Kristofer

If order is important, may be it would be easier to directly build a Seq (and use :+) – Torch

sequence(Seq(Left("a"), Left("b"))) returns Left("b") not Left("a") which would be the first failure. Therefore this does not exactly match the original specification. – Springlet

Answer 2

Given a starting sequence xs, here's my take:

xs collectFirst { case x@Left(_) => x } getOrElse
  Right(xs collect {case Right(x) => x})

This being in answer to the body of the question, obtaining only the first error as an Either[String,Seq[A]]. It's obviously not a valid answer to the question in the title

---

To return all errors:

val lefts = xs collect {case Left(x) => x }
def rights = xs collect {case Right(x) => x}
if(lefts.isEmpty) Right(rights) else Left(lefts)

Note that rights is defined as a method, so it'll only be evaluated on demand, if necessary

Lanellelanette

Does not require a downvote but second solution may leads to 2 traversal of the list, while you canseparate left from right in a single traversal – Torch

@Nicolas: True, but it's a fair trade, clarity vs premature optimisation. It's rare to see problems of this nature reach a large enough size that the performance hit would be noticable. – Lanellelanette

Answer 3

It should work:

def unfoldRes[A](x: Seq[Either[String, A]]) = x partition {_.isLeft} match {
  case (Nil, r) => Right(r map {_.right.get})
  case (l, _) => Left(l map {_.left.get} mkString "\n")
}

You split your result in left and right, if left is empty, build a Right, otherwise, build a left.

Torch

Answer 4

Here is the scalaz code:

_.sequence

Tamayo

This is an asymetric function as described in the OP (treating lefts differently from rights)!? Because there's no canonical treatment of a mixed sequence. If so, is the choice of implementation defined by the fact that the lefts are usually error messages? – Hijacker

Yes, that is the canonical example and is also the one described by the OP. An alternative implementation joins errors values with a semigroup. – Tamayo

I couldn't get this to work (using 6.0.4-SNAPSHOT) without explicitly supplying the type parameters to sequence. Otherwise, I get: Cannot prove that Either[String,Int] <:< N[B]. – Kristofer

Hi Ben, you'll probably need some type annotations. Sorry I left that off. I'll give you a more concrete example at the REPL if you can't get going. – Tamayo

By the way, I have given a 1 hour talk on this very function. I have slides but no video. I'm not sure how helpful slides will be, but here they are dl.dropbox.com/u/7810909/docs/applicative-errors-scala/… – Tamayo

This function is also mentioned in Applicative Programming With Effects (McBride, Paterson) at the end of "5 Applicative versus Monad?", since it is a good example of a Monad of an Applicative Functor. – Tamayo

Er, I am unable to edit that previous comment for some wonderful reason. What I meant to say at the end there is, a good example of "an Applicative Functor that is not a Monad" -- sorry for the muddling. – Tamayo

Answer 5

Starting in Scala 2.13, most collections are provided with a partitionMap method which partitions elements based on a function which maps items to 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 lefts:

eithers.partitionMap(identity) match {
  case (Nil, rights)       => Right(rights)
  case (firstLeft :: _, _) => Left(firstLeft)
}

// * val eithers: List[Either[String, Int]] = List(Right(1), Right(2), Right(3))
//         => Either[String,List[Int]] = Right(List(1, 2, 3))
// * val eithers: List[Either[String, Int]] = List(Right(1), Left("error1"), Right(3), Left("error2"))
//         => Either[String,List[Int]] = Left("error1")

Details of the intermediate step (partitionMap):

List(Right(1), Left("error1"), Right(3), Left("error2")).partitionMap(identity)
// => (List[String], List[Int]) = (List("error1", "error2"), List(1, 3))

Horus

Answer 6

Building on Kevin's solution, and stealing a bit from Haskell's Either type, you can create a method partitionEithers like so:

def partitionEithers[A, B](es: Seq[Either[A, B]]): (Seq[A], Seq[B]) =
  es.foldRight (Seq.empty[A], Seq.empty[B]) { case (e, (as, bs)) =>
    e.fold (a => (a +: as, bs), b => (as, b +: bs))
  }

And use that to build your solution

def unroll[A, B](es: Seq[Either[A, B]]): Either[Seq[A], Seq[B]] = {
  val (as, bs) = partitionEithers(es)
  if (!as.isEmpty) Left(as) else Right(bs)
}

Octahedral

Answer 7

I'm not used to use Either - here is my approach; maybe there are more elegant solutions:

def condense [A] (sesa: Seq [Either [String, A]]): Either [String, Seq [A]] = {
  val l = sesa.find (e => e.isLeft)
  if (l == None) Right (sesa.map (e => e.right.get)) 
  else Left (l.get.left.get)
}

condense (List (Right (3), Right (4), Left ("missing"), Right (2)))
// Either[String,Seq[Int]] = Left(missing)
condense (List (Right (3), Right (4), Right (1), Right (2)))
// Either[String,Seq[Int]] = Right(List(3, 4, 1, 2))

Left (l.get.left.get) looks a bit funny, but l itself is a Either [A, B], not an Either [A, Seq[B]], and needs rewrapping.

Cabana

You're not relying on the typing - beware the typists! – Hijacker

You mean the sesa.map, returning a list? A toSeq should fix that. – Cabana

What I meant was that you're asserting a condition in line 2 which you implicitly use in line three, where you write 'e.right.get'. E.g. the accepted answer doesn't leave the "safety of the typing". – Hijacker

I'm sorry, I can't follow. How do I leave the safety of typing? Either it is a left, then it is found by find, or it is a Right, which I can get with e.right.get; don't I? Can you provide an example, which shows the problem? – Cabana

I'm not really sure if what I'm telling makes sense at all: In the second line you assert that there is no error if l is None. Then you use this knowledge (which is in your head) to write the .get of which you know it will never fail, although .get can throw. If you look at Ben James' answer, he never calls a method that might possibly fail. – Hijacker

I have a sequence of Eithers, and call 'find' on them. Find something, which is a Left. If it finds a Left, there is a left, and Left (l.get.left.get) will wrap it in a new Left. But if there is no Left, but None, that means, all the elements in the Seq are Rights. No Lefts -> all Rights. If all of them are rights, I can collect them, pull the values out of them. That's the idea of Either - either you have a value, or something else, like an Errormessage. The knowledge is not in my head, it is in the code - you can read it. It's not phantasy. I don't see your point. – Cabana

The point is that e.g. Ben achieves the same result and he only calls methods that can never fail. Yes, your call to get will never fail because you have constructed the algorithm in a way that it works. But Ben's method can never fail because he never calls a method that could fail (throw). His code is correct (in some way) and this is asserted by the compiler. Your code is correct and this is asserted by the way you constructed your algorithm. You could negate the condition of the 'if' (by mistake) and it would still compile but not work. – Hijacker

So the problem of my code is, that if I would have written different code, it could have failed, while if Ben would have written different code, it wouldn't have compiled? If you feel comfortable with that argument from what would and could have happened ... If I would have returned an elephant, I would have returned an elephant. I don't argure against Bens solution. – Cabana

I don't want to be offensive. And I'm not calling it a problem either. It's just something that came to my mind while reading your code and I'm curious whether I am the only one noticing this - maybe it's completely irrelevant. And for the first sentence in your last comment: Yes, I think that's the purpose of type checking - failing during compilation instead of failing during runtime. And your code contains assumptions that are only verifyable during runtime. – Hijacker

@userunknown let us continue this discussion in chat – Hijacker

@Hijacker I agree. In some way it's like using an untyped collection when you have generics: it works fine (in fact exactly the same at runtime) but it's less safe. I don't think the "get" should be used, unless you are ok to use imperative style in your program, because exceptions are usually not raised in FP – Engleman

Answer 8

My answer is similar to @Garrett Rowe's: But it uses foldLeft (Also see: Why foldRight and reduceRight are NOT tail recursive?) and prepends to Seq rather than appending to Seq (See: Why is appending to a list bad?).

scala> :paste
// Entering paste mode (ctrl-D to finish)

def partitionEitherSeq[A,B](eitherSeq: Seq[Either[A,B]]): (Seq[A], Seq[B]) =
  eitherSeq.foldLeft(Seq.empty[A], Seq.empty[B]) { (acc, next) =>
  val (lefts, rights) = acc
  next.fold(error => (lefts :+ error, rights), result => (lefts, rights :+ result))
}

// Exiting paste mode, now interpreting.

partitionEitherSeq: [A, B](eitherSeq: Seq[Either[A,B]])(Seq[A], Seq[B])

scala> partitionEitherSeq(Seq(Right("Result1"), Left("Error1"), Right("Result2"), Right("Result3"), Left("Error2")))
res0: (Seq[java.lang.String], Seq[java.lang.String]) = (List(Error1, Error2),List(Result1, Result2, Result3))

Plumley