How can I create a pair of immutable Scala instances that have references to each other?

Question

I'm trying to create a simple class that represents a kind of relationship in a simple graph. Relationships are bidirectional and invertable, so if A is "above" B then B must be "below" A.

Supposing I had two instances of Relationship A (Above), and B (Below), that A.invert == B and B.invert == A. To make matters easy, I'd build both A and B from the same factory at the same time.

This is my code so far, obviously wrong:

case class Relationship(name:String, inverse:Relationship=null) {
  def setInverse(inverse:Relationship) = {
    Relationship(name, inverse)
  }
}

val foo = Relationship(name="Foo", Relationship(name="Bar"))
printf(foo.toString) // looks fine
printf(foo.inverse.toString) // null
foo.inverse.inverse = foo // totally wrong!!!

The last line is obviously invalid because it's attempting to mutate something immutable. I saw an approach that might work here, but not with case-classes? Do I have to abandon case classes if I want to make a circular reference?

How can I make two instances of Relationship, each with a property called inverse which is a reference to the other?

Edit 0: Here's my try #2 - not much better

class Relationship(name:String, _inverse:Relationship) {
  lazy val inverse = _inverse
}

val foo:Relationship = new Relationship(name="Foo", new Relationship(name="Bar", foo))
printf(foo.toString)
printf(foo.inverse.toString)

When I try this in a scala worksheet I get a java.lang.StackOverflowError, most probably because the sequence foo.inverse.inverse.inverse goes on forever. I've no way of knowing whether I actually constructed an object without preventing this infinite recursion.

Possible duplicate of [Instantiating immutable paired objects](http://stackoverflow.com/questions/7507965/instantiating-immutable-paired-objects) — bluenote10, May 24 '16 at 06:31

Simonlbc · Accepted Answer · 2016-05-24T11:53:56.453

You are right that you can't do that with a case class because of the fields of the case class that are inevitably like vals.

One solution using a class would be to define Relationship as follows:

class Relationship(name:String, _inverse: =>Relationship) {
  lazy val inverse = _inverse  //it could be defined as def as well
}                              //but good call on lazy evaluation

the only difference with your previous definition is that _inverse is "call-by-name", that is _inverse won't be evaluated until we really need to evaluate it to get a value out of it.

then you can do crazy stuff like:

scala> val a: Relationship = new Relationship("foo", new Relationship("bar", a))
a: Relationship = Relationship@695aa1

scala> a.inverse.inverse
res3: Relationship = Relationship@695aa1

or even

 scala> val a: Relationship = new Relationship("foo", a)
    a: Relationship = Relationship@14471f25
scala> a.inverse
res6: Relationship = Relationship@14471f25

EDIT for first question below: The magic appears because we have at the same time a lazy val field of the class Relationship, and because a parameter of the constructor of Relationship is call-by-name. A call-by-name parameter is reevaluated every time(like would be a def) it is called in the body of the structure it is the parameter. Now that's good because if you put it on the right side of an equality with a lazy val, the lazy val won't "call" anything on its right hand side until the lazy val is itself called. So you're saying to inverse: alright inverse, you will have to call _inverse later in the future to get its value but not now, and thus at creation of a Relationship since in the body of Relationship you're telling to evaluate nowhere _inverse until you call inverse, you never have to evaluate _inverse until you call inverse.

EDIT 2 for pattern matching: It appeared to me that you wanted to use pattern matching with your class Relationship, to do so you would have to define a companion object/extractor like this:

object Relationship {
  def unapply(r: Relationship): Option[(String, Relationship)] = 
         Some((r.name, r.inverse))
}

also you'd have to assign a val, lazy val or def that references the name parameter you give to Relationship to be able to access it from outside by defining Relationship like so for example:

class Relationship(val name: String, ...//next part same as before

then you could do nice pattern matching like so:

    scala>val a: Relationship = 
             new Relationship("foo", new Relationship("bar", a))
    a: Relationship = Relationship@31f44709

scala>a match {
     |   case Relationship("bar", aPrim) if aPrim eq a => 
                       "this is not the case here"
     |   case Relationship("foo", Relationship("bar", aPrim)) if aPrim eq a =>
                       "this is the truth"
     |   case _ => "wat"
     |}

    res1: String = this is the truth

note on above pattern matching: notice the reference equality test with eq

Okay, so the magic appears to be the => in the expression _inverse: =>Relationship. My reading of this is that you are saying that _inverse is no longer an instance of Relationship but a function which returns an instance of Relationship. But when you provide the _inverse argument you are just passing in a reference (or is it a lazy reference). — Salim Fadhley, May 24 '16 at 07:32

How can I create a pair of immutable Scala instances that have references to each other?

1 Answers1