How to avoid stackoverflow when creating immutable cross-referenced objects

I need to construct a graph like structure with references that point back to the parent. Naturally I would like to keep this structure immutable. So here is a very simplified version:

    sealed trait Empty
    object Empty extends Empty
    type MW = W | Empty
    trait E
    trait W(val parent: MW) extends E {
      def setParent(p:W): W
    }
    case class C(override val parent: MW = Empty) extends W(parent) {
      override def setParent(p: W): W = C(p)
    }
    case class Co(override val parent: MW=Empty, es:List[W]=List()) extends W(parent) {
      override def setParent(p: W): W = copy(parent = p)
      def add(w:W):Co = {
        lazy val nw:W = w.setParent(nt)
        lazy val nt = copy(es= nw :: es)
        nt
      }
    }

When I execute the following code:

    val t = plot.Co().add(plot.C())

I get a stack overflow error:

Exception in thread "main" java.lang.StackOverflowError
	at gg.Experiment3$.$anonfun$2(Experiment3.scala:360)
	at gg.Experiment3$plot$Co.nw$lzyINIT1$1(Experiment3.scala:140)
	at gg.Experiment3$plot$Co.nw$1(Experiment3.scala:140)
	at gg.Experiment3$plot$Co.nt$lzyINIT1$1(Experiment3.scala:141)
	at gg.Experiment3$plot$Co.nt$1(Experiment3.scala:141)
	at gg.Experiment3$plot$Co.nw$lzyINIT1$1(Experiment3.scala:140)
	at gg.Experiment3$plot$Co.nw$1(Experiment3.scala:140)
	at gg.Experiment3$plot$Co.nt$lzyINIT1$1(Experiment3.scala:141)
	at gg.Experiment3$plot$Co.nt$1(Experiment3.scala:141)
	at gg.Experiment3$plot$Co.nw$lzyINIT1$1(Experiment3.scala:140)
...

And this error occurs in the method:

      def add(w:W):Co = {
        lazy val nw:W = w.setParent(nt)     // line 140
        lazy val nt = copy(es= nw :: es)     // line 141
        nt
      }

I have searched the Internet and it seems like I need to use call-by-value parameters. This poses some issues: it seems like I cannot use these parameters as vals in a case class, which I need to match on. So I came up with a version that uses classes only (I assume that matching here requires that I manually code the unapply):

    type MW = W | Empty
    trait E
    abstract class W(parent: => MW) extends E {
      def setParent(p:W): W
    }
    class C(parent: => MW = Empty) extends W(parent) {
      override def setParent(p: W): W = C(p)
    }
    class Co(parent: => MW = Empty, es:List[W]=List()) extends W(parent) {
      override def setParent(p: W): W = Co(parent = p, es = es)
      def add(w: => W):Co = {
        lazy val nw:W = w.setParent(nt)
        lazy val nt = Co(parent = parent, es = nw :: es)
        nt
      }
    }

Unfortunately, I again get the same error at the same point. It seem that every time one initializes the object Co, the parent reference is followed, which case a new W to be created that leads to another Co.

How can we break the recursion? Note that I coded this in Scala3/Dotty but I assume this is solved the same way as is in Scala2.

TIA

The answer to this problem is usually to rethink your datastructures so you don’t require mutually recursive values.

What may also possibly work is if you make everything call-by-name. So at the very least also the parameter of setParent. But I’m not sure if that’s the best solution.

1 Like

What @Jasper-M said, with some elaboration.

If I understand that right, you want a Graph of immutable nodes, where every node knows its optional parent and its children. This means in a connected graph, every node can be reached from every other node. This means that if you want to add a node, you would have to update every single other node. Even if that were possible, it would be extremely costly to add a node. Also, the default implementations of equals and hashCode would stack overflow due to unbound recursion.

One solution would be to have nodes only know their parent:

case class Node(parent: Node)
case class Graph(nodes: Set[Node], children: Map[Node, Set[Node]])

Or, maybe even cleaner, nodes don’t know about connections:

case class Node(...)
case class Graph(nodes: Set[Node], parents: Map[Node, Node], children: Map[Node, Set[Node]])

Sometimes, it makes sense to introduce edges:

case class Node(...)
case class Edge(parent: Node, child: Node)
case class Graph(nodes: Set[Node], edges: Set[Edge], edgesByChild: Map[Node, Edge], edgesByParent: Map[Node, Set[Edge]])

@Jasper-M and @curoli

Thank you for the feedback.

@curoli
I see what you mean about the updates. I will play around with this but, it seems doable (2nd solution looks good).