scala - 为什么 Stream.foldLeft 在操作前要取两个元素？

Question

foldLeft 在操作之前只需要集合中的一个元素。那么它为什么要尝试解决其中两个呢？就不能再懒一点吗？

def stream(i: Int): Stream[Int] = 
  if (i < 100) {
    println("taking")
    i #:: stream(i + 1)
  } else Stream.empty

scala> stream(97).foldLeft(0) { case (acc, i) => 
  println("using")
  acc + i
}

taking
taking
using
taking
using
using
res0: Int = 294

我问这个是因为我围绕可变优先级队列构建了一个流，其中折叠的迭代可以将新成员注入(inject)流中。它从一个值开始，在第一次迭代期间注入(inject)更多值。但是这些其他值永远不会看到，因为流已经被解析为 empty。在第一次迭代之前的位置 2。

Answer 1

只能解释为什么会这样。 Here是流的 #:: 的来源(Cons):

final class Cons[+A](hd: A, tl: => Stream[A]) extends Stream[A] {
    override def isEmpty = false
    override def head = hd
    @volatile private[this] var tlVal: Stream[A] = _
    @volatile private[this] var tlGen = tl _
    def tailDefined: Boolean = tlGen eq null
    override def tail: Stream[A] = {
      if (!tailDefined)
        synchronized {
          if (!tailDefined) {
            tlVal = tlGen()
            tlGen = null
          }
        }

      tlVal
    }
  }

所以你可以看到 head总是计算出来的(不是懒惰的)。这里是 foldLeft :

override final def foldLeft[B](z: B)(op: (B, A) => B): B = {
  if (this.isEmpty) z
  else tail.foldLeft(op(z, head))(op)
}

你可以看到 tail在这里调用，这意味着“尾部的头部”(第二个元素)会自动计算(因为它需要再次调用 stream 函数来生成尾部)。所以更好的问题不是“为什么是第二个”——问题是为什么 Stream总是计算它的 第一个 元素。我不知道答案，但相信 scala-library 的实现可以通过制作 head lazy 来改进。里面 Cons , 所以你可以通过 someLazyCalculation #:: stream(i + 1) .

请注意，无论哪种方式，您的 stream函数将被调用两次，但第二种方法通过提供一些惰性值作为头，为您提供了一种避免自动第二头计算的方法。像这样的Smthng可以工作(现在不行):

def stream(i: Int): Stream[Int] = 
  if (i < 100) {
    lazy val ii = {
      println("taking")
      i
    }
    ii #:: stream(i + 1)
  } else Stream.empty

附言围绕可变集合构建(最终)不可变集合可能不是一个好主意。