scala - Lazy foldRight 提前终止混淆

Question

虽然经过Functional Programming in 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 
}

然后作者继续说明以下内容:

This looks very similar to the foldRight we wrote for List, but notice how our combining function, f, is non-strict in its second parameter. If f chooses not to evaluate its second parameter, this terminates the traversal early. We can see this by using foldRight to implement exists, which checks to see if any value in the Stream matches a given predicate.

然后作者陈述如下:

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

我的问题是组合函数 f 如何导致 exists 方法提前终止？我不认为我能够从文本中理解这是如何发生的。

Answer 1

在 f(h,t.foldRight(z)(f)) ，提供给 f 的第一个参数是 h ，第二个参数是 t.foldRight(z)(f) .一路foldRight定义是它的第二个参数f参数是一个按名称的参数，在需要之前不会被评估(并且每次需要时都会被评估)。所以在 f: (A, =>B) => B , A 类型的第一个参数是一个普通参数，但第二个是 B 类型是一个别名参数。

所以假装你定义了f像这样:

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

如果 predicate(a)则为真 b永远不需要，也永远不会被评估。这就是 or 运算符的工作方式。

所以说 exists适用于一些 Stream .对于 第一个 将被取消的元素 存在 (其中 p(h) 为真)这段代码:

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

与此代码相同(我们假设我们有一个非空流，因此我们可以删除第二种情况):

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

这相当于(扩展 f ):

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

但是 p(h)是这样的:

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

这与 true 相同。无需继续调用 foldRight ，所以提前终止发生!