懒惰的折扣,提前终止混乱

Question

虽然会虽然在斯卡拉函数式编程,我碰到下面的代码片段:

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在其第二个参数中是非严格的.如果f选择不评估其第二个参数,则会提前终止遍历.我们可以通过使用foldRight来实现exists来检查这一点,它检查Stream中的任何值是否与给定的谓词匹配.

然后作者陈述如下:

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永远不需要,永远不会被评估.这是方式或操作员的工作.

所以说exists适用于某些人Stream.对于第一被unconsed元件,将存在(其中,p(h)为true)此代码:

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,因此提前终止!