[解決済み] フォールドの早期中止

質問

フォールドを早期に終了させるにはどうしたらよいでしょうか？単純化した例として、私が(1)と(2)の数字を合計したいとします。 Iterable にある数字を合計したいが、予期しないもの（例えば奇数）に遭遇した場合、終了したいと思うかもしれません。これは最初の近似値です。

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 と return を行えば、もっときれいで明確になります)、最悪の場合、偶数でない数に遭遇した場合でも、反復可能全体をトラバースしてしまいます。

では、早期に終了するこのようなフォールドを記述する最良の方法は何でしょうか。あるいは、より受け入れられやすい方法があるのでしょうか。

どのように解決するのですか？

私の最初の選択は、通常、再帰を使用することです。 これは、ほんの少しコンパクトになり、潜在的に速くなり (確かに遅くはない)、早期終了でロジックをより明確にすることができます。 この場合、少し厄介なネストされた定義が必要です。

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] = {
  Some(nums.foldLeft(0){ (n,x) =>
    if ((n % 2) != 0) return None
    n+x
  })
}

これは、この特定のケースでは再帰よりもずっとコンパクトです（ただし、反復可能/反復子変換をしなければならなかったので、再帰は特に不運でした）。 他のすべてが同じであれば、飛び跳ねるような制御フローは避けるべきものですが、ここではそうではありません。 価値のあるケースでそれを使うことに害はありません。

もし私がこれを頻繁に行い、どこかのメソッドの中間でそれを望むなら (return を使用できないように)、私はおそらく例外処理を使用して非ローカルな制御フローを生成するでしょう。 それは結局のところ、例外処理が得意とするところであり、エラー処理だけが有用なわけではありません。 唯一のトリックはスタックトレースを生成しないことです（これは本当に遅いです）、そしてそれは簡単です。 NoStackTrace とその子である trait ControlThrowable はすでにあなたのためにそれを行っています。 Scalaはすでにこれを内部的に使っています（実際，これはfoldの内側からreturnを実装する方法です！）． 自分たちで作ってみましょう（ネストすることはできませんが、それを修正することはできます）。

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 を置くことができることに注意してください。

私にとっての次の段階は、早期終了を知らせることができるように、foldを再実装すること（私自身か、それを行うライブラリを見つけること）です。 これを行う 2 つの自然な方法は、値を伝搬させずに Option を含むもので、ここで None は終了を意味します。あるいは、完了を知らせる2番目のインジケータ関数を使用します。 Kim Stebelによって示されたScalazの遅延フォールドはすでに最初のケースをカバーしているので、私は2番目のケースを示します（mutableの実装で）。

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)(_ + _)

(再帰、リターン、怠慢などで終了を実装するかはあなた次第です)。

主な合理的なバリエーションをカバーしていると思います。他にもいくつかのオプションがありますが、なぜこのケースでそれらを使うのかはわかりません。 ( Iterator があれば、それ自体はうまくいくでしょう。 findOrPrevious があればうまくいくのですが、そうではなく、手作業でそれを行うために余分な作業が発生するため、ここで使用するのは愚かなオプションです)。