95

フォールドを早期に終了する最善の方法は何ですか? 簡単な例として、 の数値を合計したいが、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 を実行すると、はるかにクリーンで明確になります)、最悪の場合、偶数でない数に遭遇した場合でも、イテラブル全体をトラバースします。 .

では、このように早く終了する折り畳みを書く最良の方法は何でしょうか? これを再帰的に書くべきですか、それとももっと受け入れられる方法がありますか?

4

11 に答える 11

69

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

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

私の 2 番目の選択肢は、 を使用するreturnことです。これは、他のすべてをそのまま保持し、フォールドを a でラップするだけでよいため、def何かを返すことができるためです。この場合、既にメソッドがあるため、次のようになります。

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

この特定のケースでは、再帰よりもはるかにコンパクトです (反復可能/反復子変換を行う必要があったため、再帰では特に運が悪かったのですが)。他の条件がすべて同じであれば、制御フローの急な変化は避けるべきものですが、ここではそうではありません。価値がある場合に使用しても害はありません。

これを頻繁に行っていて、どこかのメソッドの途中で実行したい場合 (つまり、単に return を使用できなかった場合)、おそらく例外処理を使用して非ローカル制御フローを生成するでしょう。つまり、結局のところ、それが得意とすることであり、それが役立つのはエラー処理だけではありません。唯一の秘訣は、スタック トレースの生成を回避することです (これは非常に低速です)。これは簡単です。なぜなら、トレイトNoStackTraceとその子トレイトControlThrowableが既にそれを行っているからです。Scala はすでにこれを内部で使用しています (実際、それが折り畳みの内側からの 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

私にとっての次の行は、フォールドを再実装することです (私自身、またはそれを行うライブラリを見つけることのいずれか)。これを行う 2 つの自然な方法は、値を伝搬するのではなく、値Optionを含む に伝搬することです。ここで、Noneは終了を意味します。または、完了を通知する 2 番目のインジケーター関数を使用します。Kim Stebel が示した Scalaz の遅延フォールドはすでに最初のケースをカバーしているので、2 番目のケースを示します (ミュータブルな実装を使用):

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ではありません。手動でそれを行うには余分な作業が必要なため、ここで使用するのはばかげたオプションになります。)

于 2012-10-15T14:37:34.687 に答える
27

あなたが説明するシナリオ(望ましくない状態で終了する)は、このtakeWhile方法の良い使用例のようです。本質的には ですfilterが、条件を満たさない要素に遭遇した時点で終了する必要があります。

例えば:

val list = List(2,4,6,8,6,4,2,5,3,2)
list.takeWhile(_ % 2 == 0) //result is List(2,4,6,8,6,4,2)

これはIterators/ Iterables でも問題なく機能します。「偶数の合計ですが、奇数で中断する」に対して私が提案する解決策は次のとおりです。

list.iterator.takeWhile(_ % 2 == 0).foldLeft(...)

そして、奇数に達したときに時間を無駄にしないことを証明するために...

scala> val list = List(2,4,5,6,8)
list: List[Int] = List(2, 4, 5, 6, 8)

scala> def condition(i: Int) = {
     |   println("processing " + i)
     |   i % 2 == 0
     | }
condition: (i: Int)Boolean

scala> list.iterator.takeWhile(condition _).sum
processing 2
processing 4
processing 5
res4: Int = 6
于 2012-10-15T17:17:01.183 に答える
14

scalaz の foldRight の遅延バージョンを使用して、機能的なスタイルでやりたいことができます。詳細な説明については、このブログ投稿を参照してください。このソリューションでは を使用していますが、 を使用して効率的に をにStream変換できます。IterableStreamiterable.toStream

import scalaz._
import Scalaz._

val str = Stream(2,1,2,2,2,2,2,2,2)
var i = 0 //only here for testing
val r = str.foldr(Some(0):Option[Int])((n,s) => {
  println(i)
  i+=1
  if (n % 2 == 0) s.map(n+) else None
})

これは印刷するだけです

0
1

これは、無名関数が 2 回しか呼び出されないことを明確に示しています (つまり、奇数に遭遇するまで)。これは、foldr の定義によるもので、その署名 (の場合Stream) はdef foldr[B](b: B)(f: (Int, => B) => B)(implicit r: scalaz.Foldable[Stream]): Bです。無名関数は、2 番目の引数として名前によるパラメーターを受け取るため、評価する必要がないことに注意してください。

ところで、OP のパターン マッチング ソリューションを使用してこれを記述することもできますが、if/else と map がよりエレガントであることがわかります。

于 2012-10-15T10:10:37.793 に答える
7

まあ、Scala はローカル以外のリターンを許可します。これが良いスタイルかどうかについては、さまざまな意見があります。

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

scala> sumEvenNumbers(2 to 10)
res8: Option[Int] = None

scala> sumEvenNumbers(2 to 10 by 2)
res9: Option[Int] = Some(30)

編集:

この特定のケースでは、@Arjan が提案したように、次のこともできます。

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 _ => return None
  }
}
于 2012-10-15T10:06:30.010 に答える
1

@Rex Kerrあなたの答えは私を助けました、しかし私はどちらかを使うためにそれを微調整する必要がありました

  
  def foldOrFail [A、B、C、D](マップ:B =>どちらか[D、C])(マージ:(A、C)=> A)(初期:A)(it:反復可能[B]):どちらか[D、A] = {
    val ii = it.iterator
    varb=初期
    while(ii.hasNext){
      val x = ii.next
      map(x)match {
        case Left(error)=> return Left(error)
        ケースRight(d)=> b = merge(b、d)
      }
    }
    右(b)
  }
于 2013-03-22T20:50:48.960 に答える
1

一時変数を使用して、takeWhile を使用してみてください。これがバージョンです。

  var continue = true

  // sample stream of 2's and then a stream of 3's.

  val evenSum = (Stream.fill(10)(2) ++ Stream.fill(10)(3)).takeWhile(_ => continue)
    .foldLeft(Option[Int](0)){

    case (result,i) if i%2 != 0 =>
          continue = false;
          // return whatever is appropriate either the accumulated sum or None.
          result
    case (optionSum,i) => optionSum.map( _ + i)

  }

この場合evenSumはそうあるべきSome(20)です。

于 2015-08-04T18:32:58.520 に答える
0

より美しい解決策は、スパンを使用することです。

val (l, r) = numbers.span(_ % 2 == 0)
if(r.isEmpty) Some(l.sum)
else None

...しかし、すべての数値が偶数の場合、リストを2回トラバースします

于 2012-10-15T09:32:39.010 に答える
0

You can throw a well-chosen exception upon encountering your termination criterion, handling it in the calling code.

于 2012-10-15T09:35:14.800 に答える
0

ただ「学問的」な理由で (:

var headers = Source.fromFile(file).getLines().next().split(",")
var closeHeaderIdx = headers.takeWhile { s => !"Close".equals(s) }.foldLeft(0)((i, S) => i+1)

必要な場合は2回かかりますが、それは素晴らしいワンライナーです。「閉じる」が見つからない場合は戻ります

headers.size

別の(より良い)これは次のとおりです。

var headers = Source.fromFile(file).getLines().next().split(",").toList
var closeHeaderIdx = headers.indexOf("Close")
于 2015-06-13T17:32:20.067 に答える