尽早放弃 [英] Abort early in a fold

问题描述

提早终止弃牌的最佳方法是什么？作为一个简单的例子，假设我想总结一个 Iterable 中的数字，但是如果我遇到了我不期待的事情（比如奇数），我可能想要终止。这是第一个近似值

  def sumEvenNumbers（nums：Iterable [Int]）：Option [Int] = {
 nums.foldLeft（Some（0）：Option [Int]）{
 case（Some（s），n）if n％2 == 0 =>一些（s + n）
案例_ =>无
 
 
 $ / code> 

然而，这个解决方案相当丑陋，如果我做了.foreach和返回 - 它会更清晰和更清晰），最糟糕的是，它遍历整个迭代，即使遇到非偶数。

那么写这样一个折叠的最好方法是什么？我应该去递归地写这个，还是有一个更可接受的方式？解析方案

我的第一个选择通常是使用递归。它只是略微不那么紧凑，可能更快（当然不会更慢），并且在提前终止时可以使逻辑更加清晰。在这种情况下，您需要嵌套的defs，这有点尴尬：



  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 中折叠，这样你就可以返回一些东西了 - 在这种情况下，你已经有了一个方法，所以：



  def sumEvenNumbers（nums：Iterable [Int]）：Option [Int] = {$如果（（n％2）！= 0）返回无
 n + x 
}）b $ b某些（nums.foldLeft（0）{（n，x）=> 
） 
} 
  

在这种情况下，它比递归更紧凑（尽管我们得到了尤其是因为递归而不幸运我们必须做一个iterable / iterator转换）。当所有其他条件相同时，跳跃式控制流程是避免的，但这里不是。如果我经常这样做，并希望它在某个方法的中间（所以我不能仅仅使用它返回），我可能会使用异常处理来生成非本地控制流。毕竟，它擅长什么，错误处理不是唯一有用的时间。唯一的技巧是避免生成堆栈跟踪（这非常慢），这很容易，因为特征 NoStackTrace 及其子特征 ControlThrowable 已经为你做了。 Scala已经在内部使用它（实际上，它是如何实现从折叠中返回的！）。让我们做我们自己的（不能嵌套，但可以修复）：

pre $ import $ scala.util.control.ControlThrowable
case class返回[A]（value：A）扩展ControlThrowable {}
def快捷键[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 更好，但请注意，您可以将快捷键



接下来对我来说是重新实现fold（或者我自己或者找到一个可以实现它的库）以便它可以表示提前终止。这样做的两种自然方式是不传播值，但包含值的 Option >，其中 None 表示终止;或者使用第二个指示完成的指示符函数。 Kim Stebel展示的Scalaz懒惰的折叠已经涵盖了第一个例子，所以我将展示第二个例子（带有可变的实现）：

 <$ c $ （f：（B，A）=> B）：选项[B] = [B] （$（ii）hasNext（））{
 val ii = it.iterator 
 var b = zero 
 if（fail（x） ）return None 
b = f（b，x）
} 
一些（b）
} 
 
 def sumEvenNumbers（nums：Iterable [Int]） = foldOrFail（nums）（0）（_％2！= 0）（_ + _）
  

（无论你是通过递归，退货还是懒惰来实现终止都取决于你。）

我认为这涵盖了主要的合理变体;还有其他一些选择，但我不确定为什么会在这种情况下使用它们。如果它有一个 findOrPrevious ，但它不会，并且它所花费的额外工作（ Iterator 本身可以很好地工作手工做这件事是一个愚蠢的选择在这里使用。）

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

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?

解决方案

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

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.

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

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

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

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屋！