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

Question

作为练习,我想我会尝试在Scala中实现一个不可变的双向链表.目前,lazy vals导致堆栈溢出.有人可以解释为什么会这样吗？我很确定递归函数通常会终止,但长度为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价值.lazy vals内部是通过方法实现的,所以这是导致堆栈溢出的递归.

在没有懒惰的情况下构建循环不可变数据结构是不可能的,事实证明你的实现不够懒惰.尝试使用此结构(与您已有的完全相同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调用名称参数,并通过公共惰性val公开它们.这给了足够的懒惰来实现不可变的双向链表.在这种情况下,没有上述的递归,因为按名称调用参数意味着在读取相应节点的字段Some(addNodes(nNodes-1, newNode))之前不会计算next.

但请注意,不可变的双向链表是一种不方便的结构.为了向列表添加新元素,您必须从头开始重建它,与单链接列表相反:在单链表的前面添加元素是一个恒定时间操作,不需要重建整个清单.插入中间需要仅重建插入元素之前的部分.这就是它在功能语言中如此受欢迎的原因.双向链表需要对任何修改进行完全重建.