scala - 为什么这个不可变的双向链表实现会溢出堆栈

Question

作为练习，我想尝试在 Scala 中实现一个不可变的双向链表。目前，lazy val 导致堆栈溢出。有人可以解释为什么会这样吗？我很确定递归函数通常会终止，但是 3 的长度对于从终止函数创建溢出来说是一个非常小的数字。懒惰似乎意味着它在某个地方陷入了循环。

class Node(val prev: Option[Node], val next: Option[Node], val id: Int){
  override def toString = "["+id+"] "+next.toString
}

def addNodes(nNodes: Int, last: Node): Node = {
  if(nNodes > 0){
    lazy val newNode: Node = 
      new Node(Some(last), Some(addNodes(nNodes-1, newNode)),nNodes)
    newNode
  } else {
    new Node(Some(last), None, nNodes)
  }
}

def doublyLinked(n:Int) = {
  lazy val list: Node = new Node(None, Some(addNodes(n-2, list)),n-1)
  list
}

val x = doublyLinked(3)
println(x)

Answer 1

这里的问题不在于 addNodes，而是在于 lazy val 本身。

lazy val newNode: Node = 
      new Node(Some(last), Some(addNodes(nNodes-1, newNode)),nNodes)

为了计算newNode，你需要调用addNodes(nNodes-1, newNode)，但这意味着你需要newNode值(value)。 lazy val内部是通过方法实现的，所以这是递归导致栈溢出。

没有惰性就不可能构建循环不可变数据结构，事实证明你的实现根本不够惰性。尝试使用此结构(使用与您已有的完全相同的 addNodes 和 doublyLinked 实现):

class Node(_prev: =>Option[Node], _next: =>Option[Node], val id: Int){
  lazy val prev = _prev
  lazy val next = _next
  override def toString = s"[$id]${next.toString}"
}

这个想法是让 prev 和 next 按名称调用参数，并通过公共(public)惰性 vals 公开它们。这提供了足够的惰性来实现不可变的双向链表。在这种情况下，没有上述递归，因为按名称调用参数意味着 Some(addNodes(nNodes-1, newNode)) 在 next 之前不会被计算> 读取相应节点的字段。

但是请注意，不可变双向链表是一种不方便的结构。为了向列表中添加一个新元素，您必须从头开始重建它，这与单向链表相反:向单向链表的前面添加一个元素是一个常量时间操作，不需要重建整个列表。插入到中间只需要重建插入元素之前的部分。这就是它在函数式语言中如此受欢迎的原因。双向链表需要完全重建任何修改。