Scala: circular references in immutable data types?

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.

Critique of immutable classes with circular references design, and better options

I have a factory class that creates objects with circular references. I’d like them to be immutable (in some sense of the word) too. So I use the following technique, using a closure of sorts: [<Ab

Comparing immutable data types

Is there a commonly accepted way of how to compare immutable objects that might contain long lists of values? So far, my interfaces are as follows: interface Formula : IEquatable<Formula> { ILis

How to implement a DFS with immutable data types

I’m trying to figure out a neat way of traversing a graph Scala-style, preferably with vals and immutable data types. Given the following graph, val graph = Map(0 -> Set(1), 1 -> Set(2), 2 ->

immutable data structure in Scala

I am trying to implement an immutable data structure that models IT networks and instances (computers). Here is a simplified version: object Sample { case class Instance(id: String, flag: Boolean) ca

Is it possible to create circular references in Clojure?

Ignoring native interop and transients, is it possible to create any data structures in Clojure that contain direct circular references ? It would seem that immutable data structures can only ever con

immutable value types

I am reading Eric Liperts’ blog about Mutating Readonly Structs and I see many references here in SO to this blog as an argument why value types must be immutable. But still one thing is not clear, sa

Managing flexible, typed, immutable data structures in Scala in 2.8.x

This is a follow-up now that Scala 2.8.0 beta is out to this question: http://stackoverflow.com/questions/1710813/what-is-a-proper-way-to-manage-flexible-typed-immutable-data-structures-in-scal The ne

Resolving Circular References for Objects Implementing ISerializable

I’m writing my own IFormatter implementation and I cannot think of a way to resolve circular references between two types that both implement ISerializable. Here’s the usual pattern: [Serializable] cl

Mutable reference to immutable data

I often time hear the term Mutable reference to immutable data. In my case this was for Scala. If you have a mutable reference, wouldn’t this imply that the immutable data is mutable? I am having ha

Circular References [duplicate]

Possible Duplicate: Why are circular dependencies considered harmful? I have a line object and a point object. A line has references to two points, and each point has a reference back to the line ob

Answers

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.

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.

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.

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