7

Scala で関数型プログラミングを行っているときに、次のコード スニペットを見つけました。

def foldRight[A](z: => B)(f: (A,=>B) => B):B = uncons match {
  case Some((h,t)) => f(h,t.foldRight(z)(f))
  case None => z 
}

その後、著者は先に進み、次のように述べています。

これは List 用に書いた foldRight と非常によく似ていますが、結合関数 f の 2 番目のパラメーターが厳密ではないことに注意してください。f がその 2 番目のパラメーターを評価しないことを選択した場合、これによりトラバーサルが早期に終了します。これは、foldRight を使用して exists を実装することで確認できます。これは、ストリーム内のいずれかの値が特定の述語と一致するかどうかを確認します。

そして、著者は次のように述べています。

def exists(p: A => Boolean): Boolean =
  foldRight(false)((a, b) => p(a) || b)

私の質問は、結合関数 f がどのようにして exists メソッドで早期終了を引き起こすのですか? テキストからは、それがどのように起こるかを理解できなかったと思います。

4

1 に答える 1

7

ではf(h,t.foldRight(z)(f))、 に提供される最初の引数fはhで、2 番目の引数はt.foldRight(z)(f)です。定義方法foldRightは、そのf引数の 2 番目の引数が、必要になるまで評価されない (必要になるたびに評価される) 名前による引数であることです。したがって、f: (A, =>B) => Bでは、 type の最初の引数はA通常の引数ですが、 type の 2 番目の引数はB名前による引数です。

したがって、次のように定義したふりをfします。

f(a: A, b: => Boolean): Boolean = predicate(a) || b

predicate(a)true の場合はb必要なく、評価もされません。これがor演算子の働きです。

したがってexists、一部に適用されるとしますStream。存在する最初の要素が uncons-ed である場合( true の場合)、このコードは次のとおりです。p(h)

uncons match {
  case Some((h,t)) => f(h,t.foldRight(z)(f))
  case None => z 
}

次のコードと同じです (空でないストリームがあると想定しているため、2 番目のケースを削除できます)。

f(h,t.foldRight(z)(f))

これは（展開）と同等ですf：

p(h) || t.foldRight(z)(f)

しかし、p(h)そうです：

true || t.foldRight(z)(f)

trueそして、それは単に呼び出し続ける必要がないのと同じなfoldRightので、早期終了が発生します!

于 2013-06-27T06:44:17.920 に答える