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: 
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.
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.