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.

Ozzy

See also: #7508465, #8042856, – Calabresi

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.

Garbanzo

Regarding your last example: What happens when removing the last element? This requires a new e3 pointing to Nil. But since we can't modify e2 to point to the new e3, we also need a new e2 and consequently also e1. So we have to rebuild the list completely? – Sandal

e1, e2, e3, e4 should all be lazy val otherwise scala compiler raises "Wrong forward reference" – Mcavoy

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.

Kimsey

Answer 3

I created a blog post that describes one possible solution to your problem. http://akikhtenko.github.io/blog/2013/12/15/immutable-double-linked-tree-construction-in-scala/ It tackles trees as an example but it shouldn't be a problem to apply the idea to other data types.

Accumulator

Answer 4

Immutability in scala means that after we are finished constructing an object it should not change. During the object construction it is is actually mutable. The solution is to pass a piece of code to the constructor of the object that calculates the required values before the fields become immutable.

{
  // Create a with the creation of b as a parameter.
  val a=new A( (uncomplete:A)=>new B(uncomplete) )
}

class A( bFactory:A=>B){
  //Call the bFactory then assign the result to b.
  val b=bFactory(this);
}

class B(val a:A){
}

Since the question talks about trees I will also include the generation of a basic tree using the same technique.

 class MakeTree {
  val tree = new Node(None, createSubTree _, createSubTree _);

  def createSubTree(parent: Node): Option[Node] = {
    if (parent.depth < 3)
      Some(new Node(None, createSubNode _, createSubNode _))
    else
      None
  }
}

class Node(val parent: Option[Node], leftFactory: (Node) => Option[Node], rightFactory: (Node) => Option[Node]) {
  val left = leftFactory(this);
  val right = rightFactory(this);

  def depth(): Int = parent.map(_.depth + 1).getOrElse(0);
}

Doing the construction like this leaves a pure immutable structure without the added overhead of accessing lazy values.

Melatonin

Answer 5

class A(val b: B)
abstract class B {
  val a: A
}
new B {
  val a = new A(this)
}

Waikiki