Scala Stream 函数评估

Question

我得到了以下代码：

trait Stream[+A] {
  def uncons: Option[(A, Stream[A])]
  def foldRight[B](z: => B)(f: (A, => B) => B): B = {
    uncons.map(t => {
      f(t._1, t._2.foldRight(z)(f))
    }).getOrElse(z)
  }
  def exists(p: A => Boolean) =
    foldRight(false)((x, acc) => acc || p(x))
  def forAll(p: A => Boolean) =
    foldRight(true)((x, acc) => p(x) && acc)
}

object Stream {
  def cons[A](h: => A, t: => Stream[A]): Stream[A] =
    new Stream[A] {
      lazy val uncons = Some((h, t))
    }
}

然后我以惰性方式创建一个 Stream 并调用 exists 方法来检查评估了哪些流元素：

  println(Stream.cons({println("5"); 1}, Stream.cons({println("6"); 2}, Stream.cons({println("7"); 3}, Stream.cons({println("8"); 4}, Stream.empty)))).exists(_ == 1))

而我看到的是：

5
6
7
8
true

所以所有的元素都被评估了，尽管只有第一个就足够了。我似乎明白为什么 exists 会那样做。

然后我运行下面的代码：

println(Stream.cons({println("13"); 1}, Stream.cons({println("14"); 2}, Stream.cons({println("15"); 3}, Stream.cons({println("16"); 4}, Stream.empty)))).forAll(_ < 2))

并查看以下内容：

13
14
false

只要 forAll 遇到一个不令人满意的值，它就会终止遍历。

但为什么 forAll 那样做？它与 exists 之间的关键区别是什么？

Answer 1

有两件事需要考虑：

acc的类型
布尔表达式中 p(x) 的顺序。

懒惰

如果您将 acc 的类型更改为 B，您将无法在任何一种方法中快速失败（或短路）。您必须知道这一点，因为您的代码广泛使用了惰性，但是 => B 类型的变量只有在需要其值时才会被评估，即在某些表达式中使用。在这种情况下，acc 是通过流计算的结果的 future。这个未来只有当你试着看它时才会发生。因此，要防止评估整个流，您必须防止查看这个未来。

布尔表达式短路

这就是 p(x) 的顺序很重要的地方。在表达式 a && b 中，如果 a 是 false 那么我们知道整个合取也是 false，因此 Scala 不会尝试计算 b 因为它毫无意义.

结合两者

现在，如果您的操作数之一是惰性表达式会怎样？好吧，如果你有 lazyA || b，Scala 将从左到右读取表达式并计算 lazyA。在您的情况下， lazyA 表示下一个元素和流的其余部分的累积。因此，lazyA 扩展为 a0 :: lazyA1，后者扩展为 a0 :: a1 :: lazyA2。因此，您最终将计算整个流只是为了计算布尔二元运算的左侧部分。

现在，如果您有 a && lazyB，则扩展为 a && (b0 :: b1 :: lazyB2)。正如您在此处看到的，一旦 a 或 bi 为 false，这将 return 而不评估语句的右侧部分。这就是您的 forAll.

中发生的情况

如何修复

好消息是修复非常简单：只需交换 p(x) 和 acc 的顺序：一旦 p(x) 为 true，析取将 return 不计算 acc，停止计算。

def exists(p: A => Boolean) = foldRight(false)((x, acc) => p(x) || acc)

输出：

5
true

Scala Stream 函数评估

Scala Stream function evaluation

scala

lazy-evaluation

lazy-sequences

懒惰

布尔表达式短路

结合两者

如何修复