在折叠中提前中止 [英] Abort early in a fold

问题描述

提前终止折叠的最佳方法是什么?作为一个简化的例子，假设我想对 Iterable 中的数字求和，但如果我遇到一些我不期望的东西(比如奇数)，我可能想终止.这是第一个近似

What's the best way to terminate a fold early? As a simplified example, imagine I want to sum up the numbers in an Iterable, but if I encounter something I'm not expecting (say an odd number) I might want to terminate. This is a first approximation

def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
  nums.foldLeft (Some(0): Option[Int]) {
    case (Some(s), n) if n % 2 == 0 => Some(s + n)
    case _ => None
  }
}

然而，这个解决方案非常丑陋(例如，如果我做了一个 .foreach 和一个返回 - 它会更干净和更清晰)而且最糟糕的是，它遍历整个迭代，即使它遇到一个非-偶数.

However, this solution is pretty ugly (as in, if I did a .foreach and a return -- it'd be much cleaner and clearer) and worst of all, it traverses the entire iterable even if it encounters a non-even number.

那么写这样一个提前终止的折叠的最好方法是什么?我应该递归地写这个，还是有更可接受的方式?

So what would be the best way to write a fold like this, that terminates early? Should I just go and write this recursively, or is there a more accepted way?

推荐答案

我的第一选择通常是使用递归.它只是稍微不那么紧凑，可能更快(当然不会更慢)，并且在早期终止可以使逻辑更清晰.在这种情况下，您需要嵌套 defs，这有点尴尬:

My first choice would usually be to use recursion. It is only moderately less compact, is potentially faster (certainly no slower), and in early termination can make the logic more clear. In this case you need nested defs which is a little awkward:

def sumEvenNumbers(nums: Iterable[Int]) = {
  def sumEven(it: Iterator[Int], n: Int): Option[Int] = {
    if (it.hasNext) {
      val x = it.next
      if ((x % 2) == 0) sumEven(it, n+x) else None
    }
    else Some(n)
  }
  sumEven(nums.iterator, 0)
}

我的第二个选择是使用 return，因为它保持其他所有内容完整无缺，您只需要将折叠包装在 def 中，这样您就可以从中返回一些东西--在这种情况下，你已经有了一个方法，所以:

My second choice would be to use return, as it keeps everything else intact and you only need to wrap the fold in a def so you have something to return from--in this case, you already have a method, so:

def sumEvenNumbers(nums: Iterable[Int]): Option[Int] = {
  Some(nums.foldLeft(0){ (n,x) =>
    if ((n % 2) != 0) return None
    n+x
  })
}

在这种特殊情况下，它比递归更紧凑(尽管我们对递归特别不走运，因为我们必须进行可迭代/迭代器转换).当所有其他条件都相同时，应该避免跳跃式控制流，但这里并非如此.在有价值的情况下使用它没有坏处.

which in this particular case is a lot more compact than recursion (though we got especially unlucky with recursion since we had to do an iterable/iterator transformation). The jumpy control flow is something to avoid when all else is equal, but here it's not. No harm in using it in cases where it's valuable.

如果我经常这样做并希望它在某个方法的中间(所以我不能只使用 return)，我可能会使用异常处理来生成非本地控制流.毕竟，这就是它擅长的领域，而且错误处理并不是它唯一有用的地方.唯一的技巧是避免生成堆栈跟踪(这真的很慢)，这很容易，因为特征 NoStackTrace 及其子特征 ControlThrowable 已经为您做到了.Scala 已经在内部使用了它(实际上，这就是它实现折叠内部返回的方式！).让我们自己制作(不能嵌套，尽管可以解决这个问题):

If I was doing this often and wanted it within the middle of a method somewhere (so I couldn't just use return), I would probably use exception-handling to generate non-local control flow. That is, after all, what it is good at, and error handling is not the only time it's useful. The only trick is to avoid generating a stack trace (which is really slow), and that's easy because the trait NoStackTrace and its child trait ControlThrowable already do that for you. Scala already uses this internally (in fact, that's how it implements the return from inside the fold!). Let's make our own (can't be nested, though one could fix that):

import scala.util.control.ControlThrowable
case class Returned[A](value: A) extends ControlThrowable {}
def shortcut[A](a: => A) = try { a } catch { case Returned(v) => v }

def sumEvenNumbers(nums: Iterable[Int]) = shortcut{
  Option(nums.foldLeft(0){ (n,x) =>
    if ((x % 2) != 0) throw Returned(None)
    n+x
  })
}

这里当然使用 return 更好，但请注意，您可以将 shortcut 放在任何地方，而不仅仅是包装整个方法.

Here of course using return is better, but note that you could put shortcut anywhere, not just wrapping an entire method.

对我来说，下一步是重新实现 fold(要么是我自己，要么是找到一个可以做到这一点的库)，以便它可以发出提前终止的信号.这样做的两种自然方式是不传播值，而是传播包含该值的 Option，其中 None 表示终止；或使用指示完成的第二个指示符函数.Kim Stebel 展示的 Scalaz 懒惰折叠已经涵盖了第一种情况，所以我将展示第二种情况(具有可变实现):

Next in line for me would be to re-implement fold (either myself or to find a library that does it) so that it could signal early termination. The two natural ways of doing this are to not propagate the value but an Option containing the value, where None signifies termination; or to use a second indicator function that signals completion. The Scalaz lazy fold shown by Kim Stebel already covers the first case, so I'll show the second (with a mutable implementation):

def foldOrFail[A,B](it: Iterable[A])(zero: B)(fail: A => Boolean)(f: (B,A) => B): Option[B] = {
  val ii = it.iterator
  var b = zero
  while (ii.hasNext) {
    val x = ii.next
    if (fail(x)) return None
    b = f(b,x)
  }
  Some(b)
}

def sumEvenNumbers(nums: Iterable[Int]) = foldOrFail(nums)(0)(_ % 2 != 0)(_ + _)

(是否通过递归、返回、懒惰等方式实现终止由您决定.)

(Whether you implement the termination by recursion, return, laziness, etc. is up to you.)

我认为这涵盖了主要的合理变体；还有一些其他选择，但我不确定为什么在这种情况下会使用它们.(Iterator 本身如果有一个 findOrPrevious 就可以很好地工作，但它没有，并且手动执行此操作所需的额外工作使它成为一个愚蠢的选择在这里.)

I think that covers the main reasonable variants; there are some other options also, but I'm not sure why one would use them in this case. (Iterator itself would work well if it had a findOrPrevious, but it doesn't, and the extra work it takes to do that by hand makes it a silly option to use here.)

这篇关于在折叠中提前中止的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！