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

Question

我正在看“Scala 中的 FP”一书中的练习 5.8，问题是:

“将它们稍微推广到函数常量，它返回给定值的无限流。”

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
}

上面写着“更高效”，见 here .

我能知道为什么它更有效吗？ AFAIK，Streams 中的 cons 构造函数已经将头部和尾部标记为惰性:

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

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

Answer 1

这更像是对@ElBaulP 答案的评论，而不是对其自身权利的回答，但评论太大了。

我认为您错过了优化的根源，即使它在上面的评论中明确说明。事实证明val tail在 constant是 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 这样的实现只会创建一个类 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对象被创建。每次都会发生这种情况 tail被称为新 head .

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