What does Equivalence of instances mean?

Scala’s x == y runs x.equals(y) after checking that both x and y are not null. Scala’s compiler automatically generates equals method for case classes. That equals method compares all fields mentioned in first parameter list in primary constructor and nothing more. You can define your own equals method, but then you should also define your own hashCode method to stay with equals/hashCode contract.

case class SomeCaseClass(thisGoesIntoEquals1: Int, thisGoesIntoEquals2: String)(thisDoesntGoIntoEquals1: Char) {
  val thisDoesntGoIntoEquals2: Int = thisDoesntGoIntoEquals1.toInt
}

val instance1 = SomeCaseClass(5, "abc")('d')
val instance2 = SomeCaseClass(5, "abc")('e')
println(instance1 == instance2) // prints true

Hmmm, doesn’t the make the case class equals function useless? Two objects are equal if some of the fields are equal? Isn’t the normal semantic for equal that the object contain all the same fields and values? More me this is bizarre.

Are people happy with this?

Shouldn’t the case class equal compare its field, and then AND the result with call-next-method(), however that’s done in scala?

1 Like

If I override equals to be eq, how should I update hash code, so that two equal (i.e., eq) objects have the same hash code?

Default equals method checks instance identity:

class X(val x: Int)
val instance1 = new X(5)
val instance2 = new X(5)
println(instance1 == instance2) // prints false

so by default no fields are checked in equals.

In general it is impossible to statically generate equals that will be correct when super class change so there’s no point in even trying - people will come back complaining.

Also note that currently the same set of fields is used in:

  • instance equals
  • instance hashCode
  • instance toString
  • companion object unapply

So you can write, e.g:

case class X(a: Int, b: String)(c: Char)
val x = X(5, "abc")('d') // X.apply in action
val X(a, b) = x // X.unapply in action

Case classes in current form are very much useful. You only need to make sure you keep the fields that you want in primary constructor’s primary parameter list. In your case you must replace:

class Parent(val x: Int)

case class Child(y: String, z: Char) extends Parent(5)

with:

abstract class Parent { // or trait
  def x: Int
}
case class Child(x: Int, y: String, z: Char) extends Parent

eq compares objects’ identities, so it won’t compare any field. eq is equivalent to Java’s ==.

Yes, but isn’t that exact what I want? Two different instances of Bdd to be considered unequal?

With eq all separate instances are considered unequal, i.e. if a and b are reference types then a eq b is true if and only if a and b are the same object. In other words references a and b must point to the same place in memory.

class X(val x: Int)
val instance1 = new X(5)
val instance2 = new X(5)
println(instance1 eq instance2) // prints false, because we've created 2 objects
println(instance1 equals instance2) // prints false, because default `equals` behaves like `eq`
println(instance1 == instance2) // prints false, because `==` uses `equals` after null check

The default hashCode can be computed using System.identityHashCode if you really want.

OK, but when I try to define the equals method to use eq,

Error:(12, 16) name clash between defined and inherited member:
def equals(x$1: Any): Boolean in class Any and
override def equals(that: AnyRef): Boolean at line 12
have same type after erasure: (x$1: Object)Boolean
  override def equals(that:AnyRef):Boolean = {

There is the same mwe, while trying unsuccessfully to override the equals method.

package mwe

abstract class Bdd (val ident:Int) {}

abstract class BddTerm(ident:Int) extends Bdd(ident) {}

object BddTrue extends BddTerm(1) {}

object BddFalse extends BddTerm(0) {}

case class BddNode(label:Int, positive:Bdd, negative:Bdd) extends Bdd(Bdd.nextIdent()) {
  def equals(that:BddNode):Boolean = {
    this eq that
  }
}

object Bdd {

  var currentIdent = 2

  def nextIdent(): Int = {
    currentIdent += 1
    currentIdent - 1
  }

  def apply(label: Int): Bdd = {
    Bdd(label, BddTrue, BddFalse)
  }

  def apply(label: Int, positive: Bdd, negative: Bdd): Bdd = {
    BddNode(label, positive, negative)
  }
}

object BddTest {
  def main(args:Array[String]):Unit = {

    val bdd1a = Bdd(3,Bdd(4),BddFalse)
    val bdd1b = Bdd(3,Bdd(4),BddFalse)
    assert(! ( bdd1a eq bdd1b))
    assert(bdd1a.ident != bdd1b.ident)
    println(s"bdd1a.ident=${bdd1a.ident}")
    println(s"bdd1b.ident=${bdd1b.ident}")
    assert(! (bdd1a.equals( bdd1b)))
  }
}

Something like this compiles:

// Start writing your ScalaFiddle code here
abstract class Bdd (val ident:Int) {}

case class BddNode(label:Int, positive:Bdd, negative:Bdd) extends Bdd(Bdd.nextIdent()) {
  override def equals(that:Any):Boolean = {
    this eq that.asInstanceOf[AnyRef]
  }
  
  override def hashCode(): Int =
    System.identityHashCode(this)
}

object Bdd {
  var currentIdent = 2

  def nextIdent(): Int = {
    currentIdent += 1
    currentIdent - 1
  }
}

and gives following result:

val a = BddNode(5, null, null)
val b = BddNode(5, null, null)
println(a == b) // prints false

PS:
I’m not sure if overridding hashCode is needed. In fact fixed hashCode compiles with contract, but performance is impacted.

Thanks!!! That does the trick. But wow that’s really difficult.

Note that if you don’t care about auto generated toString then you can avoid case class:

class BddNode(val label:Int, val positive:Bdd, val negative:Bdd) extends Bdd(Bdd.nextIdent())

object BddNode {
    def apply(label: Int, positive: Bdd, negative: Bdd): BddNode =
      new BddNode(label, positive, negative)
}

If you also don’t need the apply method then you can remove it and use new keyword:

class BddNode(val label:Int, val positive:Bdd, val negative:Bdd) extends Bdd(Bdd.nextIdent())

val a = new BddNode(5, null, null)
val b = new BddNode(5, null, null)
println(a == b) // prints false

The reason for the case class is because I need pattern matching. I override toString anyway.

What about this equals method? Is it semantically as good as the one from tarsa? Advantage is that it works on principles a beginner scala programmer will understand.
Or does it have an important loophole I’m not considering?

  override def equals(that: Any): Boolean = {
    that match {
      case b: Bdd => this eq b
      case _ => false
    }
  }

Seems OK.

What does that mean?

It means that if you have e.g.:

case class X(a: String, b: String, c: String) {
  override def hashCode: Int = 1 // fixed number
}

then it’s a valid hashCode. The contract states that if two objects are equal with regard to equals method then their hash codes must also be equal. Fixed hash code satisfies that trivially.

Performance wise, fixed hash code would mean that all objects go to single hash bucket in a hash map that uses separate chaining method for collision resolution, so that hash map would degrade to linked list. Similar thing would happen with open addressing - search would always start from the same index and the consecutive checked places would be also the same.

It is – which is why it’s really fairly unusual to override equals. I’m not actually sure I’ve ever done so in real code: in general, I avoid being in a situation where I need to do so. (I consider this a very advanced feature, simply because it’s so hard to do right.)

Quite the opposite: it provides a very precise notion of “equals” – two objects are equal if and only if their primary constructor parameters match. That’s what you almost always want, if the object is immutable. (Case classes are specifically intended for self-contained, immutable data.)

And if you happen to also have some mutable data that shouldn’t be involved in equality, you put it into the secondary parameter list. I’ve used this trick occasionally in my own stuff – it’s rare, but occasionally a really useful workaround.

This bit me in the ass when I was trying to count the unique nodes in a tree using a BFS search. Counting the nodes means count the number of memory allocated nodes. I want to show (to my students) that algorithm X is more efficient than algorithm Y by counting the residual nodes as a result of algorithm X vs Y. BFS must keep a visited set. I was using a Set[Bdd], but afterwards I realized that the Set was being uniquified accorder to == which turns out to not be what I want.

Is there a way for me to have a Set[A] which does not use the equals of A but rather uses a given equivalence function? eq in my case?

And another question, which I might be confused about. In my class hierarchy I have two singleton objects called BddTrue and BddFalse which inherit from BddTerm which inherits from Bdd. The only one other instantiatable class is BddNode which inherits from Bdd. If I have a Set[Bdd] then that set will be necessarily inhabited by various nodes of BddNode and at most one BddTrue and one BddFalse. Which equivalence function is used to uniquify the BddNode instances? Is it the equals of BddTerm or is it the equals of Bdd ?

Java has java.util.IdentityHashMap - uses eq for comparing keys. Remember that eq in Scala is the same as == in Java when reading the documentation: IdentityHashMap (Java Platform SE 8 )

equals method is virtual just like any other non-static and non-private method in Java (and Scala): Virtual function - Wikipedia
With virtual methods reference type is only used to check if a method exists on receiver. Actual implementation of method that is invoked depends on instance type, not reference type.

1 Like