CODEWITHSUNDEEP
scalaimmutability
Michael Lorton
Michael Lorton

Reputation: 44406

Is it possible for a structure made of immutable types to have a cycle?

Consider the following:

case class Node(var left: Option[Node], var right: Option[Node])

It's easy to see how you could traverse this, search it, whatever. But now imagine you did this:

val root = Node(None, None)
root.left = root

Now, this is bad, catastrophic. In fact, you type it into a REPL, you'll get a StackOverflow (hey, that would be a good name for a band!) and a stack trace a thousand lines long. If you want to try it, do this:

{ root.left = root }: Unit

to suppress the REPL well-intentioned attempt to print out the results.

But to construct that, I had to specifically give the case-class mutable members, something I would never do in real life. If I use ordinary mutable members, I get a problem with construction. The closest I can come is

case class Node(left: Option[Node], right: Option[Node])
val root: Node = Node(Some(loop), None)

Then root has the rather ugly value Node(Some(null),None), but it's still not cyclic.

So my question is, if a data-structure is transitively immutable (that is, all of its members are either immutable values or references to other data-structures that are themselves transitively immutable), is it guaranteed to be acyclic?

It would be cool if it were.

Upvotes: 0

Views: 228

Answers (2)

sarveshseri
sarveshseri

Reputation: 13985

How about using lazy with call by name ?

scala> class Node(l: => Node, r: => Node, v: Int)
// defined class Node

scala> lazy val root: Node = new Node(root, root, 5)
// root: Node = <lazy>

Upvotes: 1

J&#246;rg W Mittag
J&#246;rg W Mittag

Reputation: 369526

Yes, it is possible to create cyclic data structures even with purely immutable data structures in a pure, referentially transparent, effect-free language.

The "obvious" solution is to pull out the potentially cyclic references into a separate data structure. For example, if you represent a graph as an adjacency matrix, then you don't need cycles in your data structure to represent cycles in your graph. But that's cheating: every problem can be solved by adding a layer of indirection (except the problem of having too many layers of indirection).

Another cheat would be to circumvent Scala's immutability guarantees from the outside, e.g. on the default Scala-JVM implementation by using Java reflection methods.

It is possible to create actual cyclic references. The technique is called Tying the Knot, and it relies on laziness: you can actually set the reference to an object that you haven't created yet because the reference will be evaluated lazily, by which time the object will have been created. Scala has support for laziness in various forms: lazy vals, by-name parameters, and the now deprecated DelayedInit. Also, you can "fake" laziness using functions or method: wrap the thing you want to make lazy in a function or method which produces the thing, and it won't be created until you call the function or method.

So, the same techniques should be possible in Scala as well.

Upvotes: 4

Related Questions