How can I define a custom equality operation that will be used by immutable Set comparison methods

Question

I have an immutable Set of a class, Set[MyClass], and I want to use the Set methods intersect and diff, but I want them to test for equality using my custom equals method, rather than default object equality test

I have tried overriding the == operator, but it isn't being used.

Thanks in advance.

Edit:

The intersect method is a concrete value member of GenSetLike

spec: http://www.scala-lang.org/api/current/scala/collection/GenSetLike.html src: https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_1_final/src//library/scala/collection/GenSetLike.scala#L1

def intersect(that: GenSet[A]): Repr = this filter that

so the intersection is done using the filter method.

Yet another Edit:

filter is defined in TraversableLike

spec: http://www.scala-lang.org/api/current/scala/collection/TraversableLike.html

src: https://lampsvn.epfl.ch/trac/scala/browser/scala/tags/R_2_9_1_final/src//library/scala/collection/TraversableLike.scala#L1

def filter(p: A => Boolean): Repr = {
  val b = newBuilder
      for (x <- this) 
        if (p(x)) b += x
      b.result
}

What's unclear to me is what it uses when invoked without a predicate, p. That's not an implicit parameter.

Solution 1

equals and hashCode are provided automatically in case class only if you do not define them.

case class MyClass(val name: String) {
  override def equals(o: Any) = o match {
    case that: MyClass => that.name.equalsIgnoreCase(this.name)
    case _ => false
  }
  override def hashCode = name.toUpperCase.hashCode
}

Set(MyClass("xx"), MyClass("XY"), MyClass("xX"))
res1: scala.collection.immutable.Set[MyClass] = Set(MyClass(xx), MyClass(XY))

If what you want is reference equality, still write equals and hashCode, to prevent automatic generation, and call the version from AnyRef

  override def equals(o: Any) = super.equals(o)
  override def hashCode = super.hashCode

With that:

Set(MyClass("x"), MyClass("x"))
res2: scala.collection.immutable.Set[MyClass] = Set(MyClass(x), MyClass(x))

You cannot override the ==(o: Any) from AnyRef, which is sealed and always calls equals. If you tried defining a new (overloaded) ==(m: MyClass), it is not the one that Set calls, so it is useless here and quite dangerous in general.

As for the call to filter, the reason it works is that Set[A] is a Function[A, Boolean]. And yes, equals is used, you will see that function implementation (apply) is a synonymous for contains, and most implementations of Set use == in contains (SortedSet uses the Ordering instead). And == calls equals.

---

Note: the implementation of my first equals is quick and dirty and probably bad if MyClass is to be subclassed . If so, you should at the very least check type equality (this.getClass == that.getClass) or better define a canEqual method (you may read this blog by Daniel Sobral)

Solution 2

You'll need to override .hashCode as well. This is almost always the case when you override .equals, as .hashCode is often used as a cheaper pre-check for .equals; any two objects which are equal must have identical hash codes. I'm guessing you're using objects whose default hashCode does not respect this property with respect to your custom equality, and the Set implementation is making assumptions based on the hash codes (and so never even calling your equality operation).

See the Scala docs for Any.equals and Any.hashCode: http://www.scala-lang.org/api/rc/scala/Any.html

Solution 3

This answer shows a custom mutable Set with user-defined Equality. It could be made immutable by replacing the internal store with a Vector and returning a modified copy of itself upon each operation

Comments

[Don Roby]

Have you tried just overriding .equals?

[Kareem]

I'm sorry, I left out a potentially critical point. This is case class. I implemented the change you recommended, but it doesn't have any effect. For case classes: The equals method is automatically redefined to compare two instances of the same case class structurally rather than by identity. The hashCode method is automatically redefined to use the hashCodes of constructor arguments.

[Kareem]

In addition, is .equals even used for the comparison in these methods? From the src it appears filter is used on the Set, with some unknown predicate.

[Kareem]

This did the trick, thanks! Both answers were correct, but I selected this one as it provides a full explanation.

[Daniel C. Sobral]

No, not my blog! Chapter 28 on Programming in Scala dies a much better job.

[Didier Dupont]

Sorry, I will try not do it again ;-)

[Daniel Langdon]

Small note: It's chapter 30 on the second edition of Programming in Scala

[Trylks]

What if my class is not a case class?

[Didier Dupont]

Same. The point was that as case class generates Equals/hashCode automatically, one may believe that you cannot have your own.