Scala: circular references in immutable data types?

Question

I've been thinking for a while how I would go about implementing a doubly-linked tree or list in Scala just using immutable case classes. For most "update" operations, I've been using the copy-and-update method. For example, when setting the children of a parent, i say

parent = parent.copy(child=child) 

or when setting the parent of a child, I say

child = child.copy(parent=parent) 

I realize that if i set the parent to contain a child, and then create&update a new child to contain the parent, the parent would contain a reference to the old child. Similarly, if i tried to do it the other way round, the child would contain a reference to the old parent.

I want my tree to be doubly linked so I can crawl both ways: downwards from the root to his children, or upwards from a leaf to his parents. Is it possible to "simultaneously" link the parent and child nodes in this manner, to give me the circular reference I can then crawl bi-directionally?

I could easily do this using mutable data, but in my case the doubly-linked tree will exist for a long time after creation, and I want to keep it immutable if at all possible.

Answer 1

Let's try to work it out step by step.

As a rule of thumb when creating an immutable object all constructor parameters should be known at the point of instantiation, but let's cheat and pass constructor parameters by name, then use lazy fields to delay evaluation, so we can create a bidirectional link between elements:

// p and n are passed by name  // and won't be evaluated until prev and next are accessed // for the first time class Element [T] (val value: T, p : => Element[T], n : => Element [T]) {   lazy val prev = p   lazy val next = n }  val e1:Element[Int] = new Element [Int] (1,null,e2) val e2:Element[Int] = new Element [Int] (2,e1,e3) val e3:Element[Int] = new Element [Int] (3,e2,e4) val e4:Element[Int] = new Element [Int] (4,e3,null) 

Once we run the code we will receive an immutable doubly-linked list:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null

And will be able to traverse it back and forth:

println(e1.next.next.next.value) println(e4.prev.prev.prev.value)  4 1 

Now, let's say we want to add a fifth element to the end of the list, so that it looks like this:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) ↔ e5(5) → null

val e5:Element[Int] = new Element [Int] (5,e4,null) 

At which point we get:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null                                       ↖  ↑                                        e5(5) 

Wait a minute, that doesn't look right! e4 should be pointing at e5 instead of pointing at null, but e4 is immutable and we can't change the element itself, so it looks like the only option is making a copy instead and pointing it at e3 and e5. Let's try to apply this new approach to the initial list:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null

val e4_b: Element[Int] = new Element [Int] (e4.value, // keeping original value                                              e3,e5)  val e5  : Element[Int] = new Element [Int] (5,e4_b,null) 

That's better, e4_b leads to e5 which leads back to e4_b:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null                             ↖           ↑                              e4_b(4) ↔ e5(5) 

But now we have the same original problem, just with e3 that still points at e4. Can you see a trend emerging? If we kept copying elements to fix the problem very soon we'd end up with:

null ← e1(1) ↔ e2(2) ↔ e3(3) ↔ e4(4) → null    ↑                                      ↑ e1_b(1) ↔ e2_b(2) ↔ e3_b(3) ↔ e4_b(4) ↔ e5(5) 

The original list hasn't changed a bit (as it turns we didn't call "immutable" for nothing), instead we ended up with a completely new list, albeit holding the same values. So whenever we trying to make a change to an immutable doubly linked data structure we need to rebuild the entire thing from scratch, preserving the values.

Let's take a look at Scala standard singly linked immutable list instead:

e1(1) → e2(2) → e3(3) → e4(4) → Nil

We will notice that we're able to derive new lists more easily without the need of rebuilding the entire data structure from scratch, for example to remove the second element we'd simply need to make a copy of the first and point it to the third:

e1(1) → e2(2) → e3(3) → e4(4) → Nil                  ↗          e1_b(1)  

And, of course, because the original list is immutable it didn't really change.

Answer 2

You can do it with laziness, for instance:

trait Link[A] {   def value: A   def get: Link[A] }  class Circular[A](val value: A, getter: => Link[A]) extends Link[A] {   lazy val get = getter }  object circles {   def create[A](as: (A, A)): Link[A] = {     lazy val b: Link[A] = new Circular(as._1, new Circular(as._2, b))     b   } } 

That being said, you probably want to ask yourself long and hard about why you want such a thing.