Scala and == method in recursive defined types

scala

Solution

This is easy to test yourself:

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 these give the correct answers shows that the equality check is checking for "deep" equality of subexpressions.

Furthermore, you can see in the documentation that:

For every case class the Scala compiler generates equals method which implements structural equality

"Structural equality" is the kind of deep equality checking that you are wondering about.

Finally, if you really want to see what's happening beyond on the syntactic sugar, you can use the option `-xPrint:typer` when you run `scalac` or start the REPL. If you use that option with the REPL and then declare the class `Plus`, here's what you get (shortened):

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` is calling `if l$1.==(l).&&(r$1.==(r))` in order to check equality. In other words, the generated equality method of a case class calls `==` on its subexpressions to check their equality.

Problem

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 instance, 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` result in a deep (recursive) equality test? That is, is it guaranteed that if `obj1 == obj2` holds, then `obj1` and `obj2` represent the same exact expression trees? Note that in all classes, I am relying on the default implementation of `==` (it is not overridden anywhere).

Original source