为什么 constant() 解决方案比 "FP in Scala" 5.8 中更简单的解决方案更有效？

Question

我正在看书 "FP in Scala" 中的练习 5.8，问题是：

"Generalize ones slightly to the function constant, which returns an infinite Stream of a given value."

def constant[A](a: A): Stream[A]

我的解决方案是：

def constant[A](a: A): Stream[A] =
  Stream.cons(a, constant(a))

虽然我指的是标准解决方案，但它是：

// This is more efficient than `cons(a, constant(a))` since it's just
// one object referencing itself.
def constant[A](a: A): Stream[A] = {
  lazy val tail: Stream[A] = Cons(() => a, () => tail) 
  tail
}

表示 "more efficient"，参见 here。

请问为什么效率更高？ AFAIK，Streams 中的 cons 构造函数已经将 head 和 tail 标记为惰性：

def cons[A](hd: => A, tl: => Stream[A]): Stream[A] = { 
  lazy val head = hd 
  lazy val tail = tl 
  Cons(() => head, () => tail) 
}

为什么我们还需要再次将尾巴标记为懒惰？我不太明白这里的意思。

Answer 1

我认为是因为在延迟实现中，你只创建了一次对象，并把它记忆了，所以当你调用constant时，你指的是一遍又一遍地指向同一个对象，就像这样：

tail -----
  ^------'

通过您的实现（这与我在阅读本书时遇到的相同），您每次调用该函数时都在创建新对象。所以如果你多次调用你的实现，你有：

Stream.cons(a, Stream.cons(a, Stream.cons(a, constant(a))))

举个例子来看:

def constant[A](a: A): Stream[A] = { println("CALLED"); cons(a, constant(a)) }

// This is more efficient than `cons(a, constant(a))` since it's just
// one object referencing itself.
def constant_1[A](a: A): Stream[A] = {
   lazy val tail: Stream[A] = Cons(() ⇒ a, () ⇒ tail)
   println("CALLED_1")
   tail
  }

println(s"Cons ${Stream.constant_1(0).take(10).toListFast}")
println(s"Cons ${Stream.constant(0).take(10).toListFast}")

以上代码产生以下输出：

CALLED_1
Cons List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
CALLED
Cons List(0, 0, 0, 0, 0, 0, 0, 0, 0, 0)

可以看到，惰性实现的println语句只调用了一次

详细的解释可以看@SergGr。

Answer 2

这更多是对@ElBaulP 回答的评论，而不是对它本身的回答，但它对于评论来说太大了。

我认为您错过了优化的根源，尽管上面的评论中明确指出了这一点。 constant 中的 val tail 是 lazy 这一事实是一个实现细节，或者更确切地说是一个使优化的主要来源成为可能的技巧。优化的主要来源是 tail 是自引用的。

暂时让我们摆脱所有 lazy 的东西。假设 Cons 定义为

case class Cons[+A](h: A, t: () => Stream[A]) extends Stream[A]

然后我们将 constant 定义为

def constant[A](a: A): Stream[A] = {
   val tailFunc: () => Stream[A] =  () => tail
   val tail: Stream[A] = Cons(a, tailFunc)
   tail
}

是的，这是一个语法无效的程序，因为 tailFunc 使用仅在下一行定义的 tail。但想象一下 Scala 可以编译它。我认为现在很清楚 constant 的这种实现每次调用只会创建一个 class Cons 的实例，并且无论您尝试迭代多长时间都会使用该实例返回的流。

将 tail 定义为 lazy 所允许的只是使代码在逻辑上等同于上述代码，编译无误。从实现的角度来看，它类似于这样的东西：

class Lazy[A](var value:A)

def constant[A](a: A): Stream[A] = {
   val lazyTail: Lazy[Stream[A]] = new Lazy(null)
   // this tailFunc works because lazyTail is already fixed and can be safely 
   // captured although lazyTail.value will be changed
   val tailFunc: () => Stream[A] =  () => lazyTail.value 
   lazyTail.value = new Stream(a, tailFunc)
   lazyTail.value
}

此代码在许多细节上与实际 lazy 实现不完全匹配，因为它实际上很急切，但我认为它表明您并不真正需要 lazy 来进行优化（但以使用 var 为代价，Scala 编译器在其真实的、更复杂的 lazy 实现中无论如何都会这样做）。

在您天真的实现中

def constant[A](a: A): Stream[A] =  Stream.cons(a, constant(a))

tail 的惰性求值让您不会因为 constant 自身的递归调用而立即因堆栈溢出而失败。但是，当您执行 constant(whatever).tail 时，tail 仍会被计算，因此会再次调用 constant 方法并创建一个新的 Cons 对象。每次在新 head 上调用 tail 时都会发生这种情况。

再次声明，lazy val tail 只是一个技巧，允许 tail 在创建时引用自己，真正重要的部分是 tail 引用自己这允许只使用一个对象进行迭代，而不是每个下一个 .tail 调用一个对象。

为什么 constant() 解决方案比 "FP in Scala" 5.8 中更简单的解决方案更有效？

Why the constant() solution is more efficient than the easier one in "FP in Scala" 5.8?

functional-programming

scala

lazy-evaluation