在Scala中，为什么递归惰性列表会导致栈溢出？

Question

我在Meta PPCG上看到了这篇答案，由proud haskeller编写的Haskell代码片段如下：

x=2:x

我想：“等一下，我可以用Scala做到这个！”于是我尝试了：

lazy val x: List[Int] = 2 :: x

它已经编译成功了，我的控制台也打印出了一个不错的x: List[Int] = <lazy>。但是每一行都会导致StackOverflowException异常：

x take 1
x.head
x(1)
x

根据上面的内容，似乎任何尝试使用x都会在计算x时导致堆栈溢出（或在控制台中打印时发生堆栈溢出）。在这个例子中，Scala的惰性与Haskell的惰性有什么不同？这是Scala的lazy val的一个特性，还是List类只需要一个完整的尾部？

- Brian McCutchon

Answer 1

你想要的是 def x: Stream[Int] = 2 #:: x。这将产生一个 immutable.Stream[Int]。

懒变量只在需要时进行评估，但它会被完全评估。而Stream是一组惰性值。每个元素只在需要时才被评估，但整个集合可能永远不会被评估，这就是为什么它可以是无限的。

- jwvh

---

还不够，你需要返回类型才能编译通过，但还是很好的。使用lazy vals可以这样写：lazy val x: Stream[Int] = 2 #:: x。 - Brian McCutchon

@BrianMcCutchon，你说得对。我正忙着写第二段，错过了那个问题。然而，我认为将“Stream”值设为lazy没有太大意义。如果它是一个“val”，那么结果（已评估的元素）会被记忆化。如果它是一个“var”，则不会。将其设置为“lazy val”并不能带来太多好处。 - jwvh

哎呀，又打错字了，试图阐明val流和被记忆的def（而不是var）流之间的区别。 - jwvh

Answer 2

好的，看起来我在提出问题时找到了答案。这似乎更多是与List有关而非lazy val。为了尝试这个解决方案，我制作了一个简单的LazyList实现：

class LazyList(h: Int, t: => LazyList) {
  val head = h
  lazy val tail = t
}

那么我可以这样做：

lazy val x: LazyList = new LazyList(1, x)
x.head // 1
x.tail.tail.tail.head // 1

所以，Scala的惰性确实非常懒，如果你让所有东西都变得惰性的话。

- Brian McCutchon

---

请注意，如果您在Haskell中使用了严格列表，将会发生完全相同的事情。 - Jörg W Mittag

@JörgWMittag 很有趣。我对 Haskell 了解甚少，但我很惊讶它有一个严格的列表类型。 - Brian McCutchon