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!

Give it a kudos