Scala Stream按需调用(惰性)与按名称调用

Question

所以我知道call-by-need只是call-by-name的一个记忆版本。在Martin Odersky关于Coursera的FP课程7.3 (惰性评估)中，他提到如果Streams是使用call-by-name实现的，那么它可能会导致计算复杂性的激增。

这种井喷的例子是什么？

按名称调用：

def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
  def head = hd
  def tail = tl
  ...
}

按需调用：

def cons[T](hd: T, tl: => Stream[T]) = new Stream[T] {
  def head = hd
  lazy val tail = tl
  ...
}

Answer 1

例如斐波那契级数，通过添加前两个元素形成后继者来实现。如果没有记忆化，序列的长度将线性减速(和堆栈增长)：

scala> lazy val fib: Stream[Int] = Stream.cons(0,
     | Stream.cons(1, fib.zip(fib.tail).map(p => p._1 + p._2)))
fib: Stream[Int] = Stream(0, ?)

延迟复制自this blog的示例(-sic-)

Answer 2

def和lazy val都很懒。不同之处在于，每次调用def时都会重新计算它。lazy val只在第一次被调用时被求值，并且对它的任何调用都只查看第一个求值的值。

使用def意味着每次调用tail时都要对其进行重新计算。

def randDef: () => Int = {
  val r = scala.util.Random.nextInt
  () => r
}

val randVal: () => Int = {
  val r = scala.util.Random.nextInt
  () => r
}

lazy val randLazyVal: () => Int = {
  val r = scala.util.Random.nextInt
  () => r
}
// defined function randDef
// randVal: () => Int = ammonite.$sess.cmd18$Helper$$Lambda$2545/0x00000008013a4430@7466fa3
// randLazyVal: () => Int = [lazy]

randDef()
// res8: Int = -693604502
randDef()
// res9: Int = 2056941756
randDef eq randDef
// res15: Boolean = false

randVal()
// res11: Int = 3
randVal()
// res12: Int = 3
randVal eq randVal
// res16: Boolean = true

randLazyVal()
// res13: Int = 99
randLazyVal()
// res14: Int = 99
randLazyVal eq randLazyVal
// res17: Boolean = true