# An immutable circular graph in scala

5 Jan 2015

I was building a state machine in Scala, and I want it to be an immutable state machine, where all nodes are immutable. It's actually a bit interesting how we can achieve it in Scala.

Let's define something first:

A node consists of an edges that point to another node

and

An immutable node cannot be added more edges

Now, say, you want to build a graph where `A` -> `B` and `B` -> `A`. You have a dilemma that you don't know whether you should create A or B first. You cannot create A without B and you cannot create B without A.

## The simple solution

Use some sort of pointers. For example, `A` contains an edge which points to the string “B”. Then, we have a `Map` which maps “B” to the node `B`.

But it's a bit hideous, isn't it?

## The lazy solution

We use `lazy`; It's already some sort of pointer. When we pass a lazy variable to a pass-by-name argument, the value is not yet initialised until it is used. That can be our solution

Let's define the Node class first:

```class Node(nextNode: => Node) { private lazy val evaluatedNextNode = nextNode def next = evaluatedNextNode } ```

Please note that `lazy val evaluatedEdges` is very important because a pass-by-name argument is evaluated everytime it is used; That can be very expensive.

Ok, now we can do this:

```class Graph { lazy val a: Node = new Node(b) lazy val b: Node = new Node(a) } ```

Then:

```val g = new Graph g.a.next == g.b // true g.b.next == g.a // true ```

Actually, this looks hideous too…. but it's an AWESOME use of `lazy`!