scala - Why does this immutable doubly linked list implementation overflow the stack -

as exercise thought i'd try , implement immutable doubly linked list in scala. @ moment lazy vals causing stack overflow. can explain why happening? i'm pretty sure recursive function terminate, length of 3 small number create overflow terminating function. seems laziness means it's getting stuck in 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) 

the problem here not addnodes, it's lazy val itself.

lazy val newnode: node =        new node(some(last), some(addnodes(nnodes-1, newnode)),nnodes) 

in order compute newnode, need call addnodes(nnodes-1, newnode), means need newnode value. lazy vals internally implemented via methods, recursion causes stack overflow.

it impossible build circular immutable data structures without laziness, , turns out implementation not lazy enough. try using structure (with same addnodes , doublylinked implementation 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 make prev , next call-by-name parameters , expose them through public lazy vals. gives enough laziness implement immutable doubly-linked list. in case there no recursion described above, because call-by-name parameter means some(addnodes(nnodes-1, newnode)) won't computed until next field of corresponding node read.

note, however, immutable doubly-linked list inconvenient structure. in order add new element list have rebuild scratch, contrary singly-linked list: adding element front of singly-linked list constant-time operation not require rebuilding whole list. inserting middle requires rebuilding part before inserted element. that's why popular in functional languages. doubly-linked list requires full rebuild on any modification.