Why does this immutable doubly linked list implementation overflow the stack

Question

As an exercise I thought I'd try and implement an immutable doubly linked list in Scala. At the moment the lazy vals are causing a stack overflow. Can someone explain why this is happening? I'm pretty sure the recursive function would usually terminate, but a length of 3 is a very small number to create an overflow from a terminating function. It seems something about the laziness means that it's getting stuck in a loop somewhere.

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

The problem here is not with addNodes, it's with lazy val itself.

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

In order to compute newNode, you need to call addNodes(nNodes-1, newNode), but it means that you need newNode value. lazy vals internally are implemented via methods, so this is the recursion which causes stack overflow.

It is impossible to build circular immutable data structures without laziness, and it turns out that your implementation is simply not lazy enough. Try using this structure (with exactly the same addNodes and doublyLinked implementation you already have):

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}"
}

The idea is to make prev and next call-by-name parameters and expose them through public lazy vals. This gives just enough laziness to implement immutable doubly-linked list. In this case there is no recursion described above, because call-by-name parameter means that Some(addNodes(nNodes-1, newNode)) won't be computed until next field of the corresponding node is read.

Note, however, that immutable doubly-linked list is an inconvenient structure. In order to add a new element to the list you will have to rebuild it from scratch, contrary to singly-linked list: adding an element to the front of a singly-linked list is a constant-time operation which does not require rebuilding the whole list. Inserting into the middle requires rebuilding only the part before the inserted element. That's why it is so popular in functional languages. Doubly-linked list requires full rebuild on any modification.