Equality relations in Scala

Question

I just stumbled on one of Tony Morris' blog-posts about Java and a fundamental problem with the language: that of defining a bespoke equality-relation for a collection. This is something that I think is a big deal and wondered whether there was some scala solution.

The classic issue manifests itself in thinking about, say, a trade. Let's say I make two trades of +100 vodafone shares @150p. The two trades are equal, yes? Except they are not the same trade. In the case of a normal real-world system, with persistence or serialization, I cannot rely on identity to tell me whether two references are to the same trade!

So what I want is to be able to create a collection which I can pass an Equality-relation to:

val as = CleverSet[Trade](IdEquality)
val bs = CleverSet[Trade](EconomicsEquality)

How would I implement my set in an efficient manner (unless the EqualityRelation also defines a hash mechanism)?

trait EqualityRelation[T] {
  def equal(t1: T, t2: T) : Boolean
  def hash(t: T) : Int
}

So the questions are:

• Is there a library which provides this ability?
• Is there some way of doing this neatly in Scala?

It seems that with implicits, it would be quite an easy thing to add to the existing scala Set type.

Answer 1

This can already be achieved with Java's TreeSet and a Comparator implementation:

TreeSet<String> ignoreCase = new TreeSet<String>(new Comparator<String>(){
    @Override
    public int compare(String o1, String o2) {
        return o1.compareToIgnoreCase(o2);
    }});

TreeSet<String> withCase = new TreeSet<String>();

List<String> values = asList("A", "a");
ignoreCase.addAll(values);
withCase.addAll(values);

Output:

ignoreCase -> [A]
withCase -> [A, a]

This has the drawbacks that the Comparator to implement is more powerful than needed and that you're restricted to collections that support Comparators. As pointed out by oxbow_lakes the Comparator implementation breaks the Set contract (for !a.equals(b) it could be that new Set(); set.add(a) == true && set.add(b) == false).

Scala supports this with a view transformation from A => Ordered[A].

scala> new scala.collection.immutable.TreeSet[String]()(x=> x.toLowerCase) + "a"
 + "A"
res0: scala.collection.immutable.TreeSet[String] = Set(A)

Answer 2

You're describing the concept of a hashing strategy. The Trove library includes sets and maps that can be constructed with hashing strategies.

Answer 3

I know you're asking about Scala, but it's worth comparing with what the .Net collections offer. In particular, all Hash-based collections (eg Dictionary<TKey, TValue> and HashSet<T>) can take an instance of IEqualityComparer<T>. This is similar to Scala's Equiv[T], but also supplies a custom hash code. You could create a similar trait by subclassing Equiv:

trait HashEquiv[T] extends Equiv[T] {
  def hashOf(t: T) : Int
}

To be fully supported, hash based collections would need to add HashEquiv implicit parameters to their construction and use the implicitly imported equiv and hashOf methods instead of the Object instance methods (like TreeSet, etc do with the Ordered trait, but in reverse). There would also need to be an implicit conversion from Any to HashEquiv that uses the intrinsic equals and hashCode implementation.