Scala Stream 按需调用(懒惰)与按名称调用 [英] Scala Stream call-by-need (lazy) vs call-by-name

问题描述

所以我知道按需求调用只是按名称调用的记忆版本.在 Martin Odersky 在 Coursera 上的 FP 课程的第 7.3 课(懒惰评估)中，他提到如果使用按名称调用来实现 Streams，那么它可能会导致计算复杂性激增.

So I understand that call-by-need is simply a memoized version of call-by-name. In Martin Odersky's FP Course on Coursera, in lecture 7.3 (Lazy Evaluation), he mentions that if Streams were implemented using call-by-name, then it could potentially lead to a blowup in computational complexity.

这种爆炸的例子是什么?

What would be an example of such a blowup?

按姓名呼叫:

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
  ...
}

推荐答案

例如斐波那契数列，通过添加前两个元素形成后继者来实现.如果没有记忆，序列的长度会线性放缓(和堆栈增长):

For example the Fibonacci series, implemented by adding the previous two elements to form the successor. Without memoization, that would have a linear slowdown (and stack growth) in the length of the sequence:

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, ?)

从 这个博客

这篇关于Scala Stream 按需调用(懒惰)与按名称调用的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！