Scala and == method in recursive defined types

Question

I know that the == method in Scala has the same semantics of the equals method in Java. However, I would like to understand when applied to instances of recursive structures. For example, consider a bunch of expressions:

 abstract class Exp abstract class BinaryExp(l:Exp, r:Exp) extends Exp case class Plus(l:Exp, r:Exp) extends BinaryExp(l,r) case class Minus(l:Exp, r:Exp) extends BinaryExp(l,r) case class Mult(l:Exp, r:Exp) extends BinaryExp(l,r) case class Div(l:Exp, r:Exp) extends BinaryExp(l,r) case class Num(v:Int) extends Exp 

Then, when I have two instances of a BinaryExp , say obj1 and obj2 , does obj1 == obj2 perform a deep (recursive) equality test? That is, is it guaranteed that if obj1 == obj2 is satisfied, then obj1 and obj2 represent the same expression trees?

Note that in all classes I rely on the standard implementation == (it is not redefined anywhere).

Answer 1

This is easy to verify on your own:

 val x = Plus(Num(1), Num(2)) val y = Plus(Num(1), Num(2)) val z = Plus(Num(1), Num(3)) println(x == y) // prints true println(x == z) // prints false 

The fact that they give the correct answers shows that the equality check checks the "deep" equality of subexpressions.

In addition, you can see in the documentation that:

For each case class, the Scala compiler generates an equals method that implements structural equality

"Structural equality" is a kind of deep equality test that you are interested in.

Finally, if you really want to see what happens next on syntactic sugar, you can use the -xPrint:typer when running scalac or running REPL. If you use this parameter with REPL and then declare a Plus class, here is what you get (in abbreviated form):

 scala> case class Plus(l:Exp, r:Exp) extends BinaryExp(l,r) [[syntax trees at end of typer]]// Scala source: <console> ... case class Plus extends $line2.$read.$iw.$iw.BinaryExp with ScalaObject with Product with Serializable { ... override def equals(x$1: Any): Boolean = Plus.this.eq(x$1.asInstanceOf[java.lang.Object]).||(x$1 match { case (l: $line1.$read.$iw.$iw.Exp, r: $line1.$read.$iw.$iw.Exp)$line3.$read.$iw.$iw.Plus((l$1 @ _), (r$1 @ _)) if l$1.==(l).&&(r$1.==(r)) => x$1.asInstanceOf[$line3.$read.$iw.$iw.Plus].canEqual(Plus.this) case _ => false }); 

So, buried in the first case , you'll see that Plus.equals calls if l$1.==(l).&&(r$1.==(r)) to check for equality. In other words, the generated case equality method calls == in its subexpressions to verify that they are equal.