如何将Seq[Either[A,B]]缩减为Either[A,Seq[B]]？

Question

给定一个由 Seq[Either[String,A]] 组成的序列，其中Left代表错误消息。我想获得一个Either[String,Seq[A]]，如果序列的所有元素都是Right，那么我将获得一个Right（它将是一个Seq[A]）。如果至少有一个Left（表示错误消息），我想获取第一个错误消息或所有错误消息的连接。

当然你可以发布使用cats或scalaz库的代码，但我也对不使用这些库的代码感兴趣。

编辑

我已更改标题，原来要求的是Either[Seq[A], Seq[B]]，以反映消息正文。

- ziggystar

Answer 1

编辑：我错过了你问题标题中提到的Either[Seq[A], Seq[B]]，但我读到了 "我想要获取第一个错误信息或所有错误信息的连结"，这将会给你前者：

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)

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

- Ben James

---

这比我的解决方案更短，使用了匹配。我认为你可以使用for-comprehension使折叠函数更易读。 - ziggystar

是的，您可以将 foldLeft 函数的主体替换为以下内容：for (xs <- acc.right; x <- e.right) yield x :: xs。 - Ben James

如果顺序很重要，直接构建一个Seq（并使用:+）可能会更容易。 - Nicolas

sequence(Seq(Left("a"), Left("b"))) 返回的是 Left("b") 而不是第一个失败的 Left("a")。因此，这并不完全符合原始规范。 - sim642

Answer 2

假设有一个起始序列xs，这是我的想法：

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

针对问题主体所回答的内容，获取只返回第一个错误的Either[String,Seq[A]]。显然这不是对标题问题的有效回答。

---

要返回所有错误：

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

请注意rights被定义为一个方法，因此它只会在需要时按需求进行评估。

- Kevin Wright

---

不需要进行投票，但第二种解决方案可能会导致对列表的两次遍历，而你可以在单次遍历中将左侧与右侧分开。 - Nicolas

@Nicolas：没错，但这是一种公平的权衡，清晰度与过早优化之间。很少见到此类问题达到足够大的规模，以至于性能损失会明显可见。 - Kevin Wright

Answer 3

应该可以工作：

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

将结果分为左侧和右侧，如果左侧为空，则构建一个右侧，否则，构建一个左侧。

- Nicolas

Answer 4

这里是scalaz代码： _.sequence

- Tony Morris

---

这是一个非对称函数，正如OP中所描述的那样（将左侧与右侧不同地处理）！因为没有混合序列的规范处理方式。如果是这样，那么实现的选择是否由于左侧通常是错误消息所定义？ - ziggystar

是的，那是规范示例，也是由 OP 描述的示例。另一种实现方式是使用半群将错误值连接起来。 - Tony Morris

我无法在使用6.0.4-SNAPSHOT时使其正常工作，除非显式地向“sequence”提供类型参数。否则，我会得到：“Cannot prove that Either[String,Int] <:< N[B]”。 - Ben James

嗨Ben，你可能需要一些类型注释。很抱歉我漏掉了它。如果你无法开始，请在REPL中给你一个更具体的示例。 - Tony Morris

顺便说一下，我已经就这个函数做了一个小时的演讲。我有幻灯片但没有视频。我不确定幻灯片会有多大帮助，但是在这里它们是http://dl.dropbox.com/u/7810909/docs/applicative-errors-scala/applicative-errors-scala/chunk-html/index.html - Tony Morris

Answer 5

从Scala 2.13开始，大多数集合都提供了一个partitionMap方法，它根据将项目映射到Right或Left的函数对元素进行分区。

在我们的情况下，我们甚至不需要一个将输入转换为Right或Left的函数来定义分区，因为我们已经有了Rights和Lefts。因此，简单地使用identity！

然后，根据是否存在左侧，只需匹配左侧和右侧的分区元组即可。

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

中间步骤的细节（partitionMap）：

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

- Xavier Guihot

Answer 6

在Kevin的解决方案基础上，再从Haskell的Either类型中借鉴一些技巧，你可以创建一个名为partitionEithers的方法，实现如下：

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

使用它来构建你的解决方案。

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

- Garrett Rowe

Answer 7

我不习惯使用 Either - 这是我的方法；也许有更优雅的解决方案：

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) 看起来有点奇怪，但是 l 本身是一个 Either [A, B]，而不是 Either [A, Seq[B]]，需要重新包装。

- user unknown

---

你不要过分依赖打字 - 小心打字员！ - ziggystar

我的意思是，你在第2行断言了一个条件，而你在第三行中隐式地使用了它，即你写的'e.right.get'。例如，被接受的答案不会离开“类型的安全性”。 - ziggystar

我不确定我说的是否有意义：在第二行中，您断言如果“l”为“None”，则没有错误。然后，您使用这个已知信息（在您的头脑中）编写了.get，您知道它永远不会失败，尽管.get可能会抛出异常。如果您查看Ben James的答案，他从未调用可能会失败的方法。 - ziggystar

所以我的代码问题在于，如果我写了不同的代码，它可能会失败，而如果Ben写了不同的代码，它就不会编译？如果你对从可能发生和本应发生的情况的论点感到舒适...如果我返回一只大象，那我就会返回一只大象。我不反对Ben的解决方案。 - user unknown

@ziggystar 我同意。某种程度上，这就像在使用泛型时使用未类型化的集合：它可以正常工作（实际上在运行时完全相同），但不够安全。我认为“get”不应该被使用，除非你在程序中使用命令式风格，因为在FP中通常不会引发异常。 - Sebastien Lorber

Answer 8

我的答案与@Garrett Rowe的类似：但它使用了foldLeft（也请参见：为什么foldRight和reduceRight不是尾递归？），并且将元素前置到Seq而不是追加到Seq（请参见：为什么向列表追加元素是不好的？）。

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

- Sudheer Aedama