by Tomas Mikula on Apr 02, 2017
technical
This is a guest post by Tomas Mikula. It was initially published as a document in the hasheq. It has been slightly edited and is being republished here with the permission of the original author.
This article describes what we mean when we say that the data structures in this library are equivalence-aware in a type-safe fashion.
Set is a data structure that doesn’t contain duplicate elements. An implementation of Set must therefore have a way to compare elements for “sameness”. A useful notion of sameness is equivalence, i.e. a binary relation that is reflexive, symmetric and transitive. Any reasonable implementation of Set is equipped with some equivalence relation on its element type.
Here’s the catch: For any type with more than one inhabitant there are multiple valid equivalence relations. We cannot (in general) pick one that is suitable in all contexts. For example, are these two binary trees same?
+ +
/ \ / \
1 + + 3
/ \ / \
2 3 1 2
It depends on the context. They clearly have different structure, but they are both binary search trees containing the same elements. For a balancing algorithm, they are different trees, but as an implementation of Set, they represent the same set of integers.
Despite the non-uniqueness, there is one equivalence relation that stands out: equality. Two objects are considered equal when they are indistinguishable to an observer. Formally, equality is required to have the substitution property:
\[ \forall a,b \in A, \forall f \in (A \to B): a=_A b \implies f(a)=_B f(b) \]
(Here, $=_A$ denotes equality on $A$, $=_B$ denotes equality on $B$.)
Equality is the finest equivalence: whenever two elements are equal, they are necessarily equivalent with respect to every equivalence.
Popular Scala libraries take one of these two approaches when dealing with comparing elements for “sameness”.
The current approach of cats is equality.
Instances of the cats.Eq[A] typeclass are required to have all the properties of equality, including the substitution property above.
The problem with this approach is that for some types, such as Set[Int], equality is too strict to be useful:
Are values Set(1, 2) and Set(2, 1) equal?
For that to be true, they have to be indistinguishable by any function.
Let’s try (_.toList):
scala> Set(1, 2).toList == Set(2, 1).toList
res0: Boolean = false
So, Set(1, 2) and Set(2, 1) are clearly not equal.
As a result, we cannot use Set[Int] in a context where equality is required (without cheating).
On the other hand, scalaz uses unspecified equivalence.
Although the name scalaz.Equal[A] might suggest equality, instances of this typeclass are only tested for properties of equivalence.
As mentioned above, there are multiple valid equivalence relations for virtually any type.
When there are also multiple useful equivalences for a type, we are at risk of mixing them up (and the fact that they are usually resolved as implicit arguments only makes things worse).
Let’s look at how we deal with this issue. We define typeclass Equiv with an extra type parameter that serves as a “tag” identifying the meaning of the equivalence.
trait Equiv[A, Eq] {
def equiv(a: A, b: A): Boolean
}
// defined trait Equiv
For the compiler, the “tag” is an opaque type. It only has specific meaning for humans. The only meaning it has for the compiler is that different tags represent (intensionally) different equivalence relations.
An equivalence-aware data structure then carries in its type the tag of the equivalence it uses.
import hasheq._
// import hasheq._
import hasheq.immutable._
// import hasheq.immutable._
import hasheq.std.int._
// import hasheq.std.int._
scala> HashSet(1, 2, 3, 4, 5)
res0: hasheq.immutable.HashSet[Int] = HashSetoid(5, 1, 2, 3, 4)
What on earth is HashSetoid?
A setoid is an equivalence-aware set.
HashSetoid is then just a setoid implementated using hash-table.
Let’s look at the definition of HashSet:
type HashSet[A] = HashSetoid[A, Equality.type]
So HashSet is just a HashSetoid whose equivalence is equality.
To create an instance of HashSet[Int] above, we needed to have an implicit instance of Equiv[Int, Equality.type] in scope.
implicitly[Equiv[Int, Equality.type]]
For the compiler, Equality is just a rather arbitrary singleton object.
It only has the meaning of mathematical equality for us, humans.
There is a convenient type alias provided for equality relation:
type Equal[A] = Equiv[A, Equality.type]
implicitly[Equal[Int]]
So how do we deal with the problem of set equality mentioned above, i.e. that HashSet(1, 2) and HashSet(2, 1) are not truly equal?
We just don’t provide a definition of equality for HashSet[Int].
scala> implicitly[Equal[HashSet[Int]]]
<console>:22: error: could not find implicit value for parameter e: hasheq.Equal[hasheq.immutable.HashSet[Int]]
implicitly[Equal[HashSet[Int]]]
^
But that means we cannot have a HashSet[HashSet[Int]]!
(Remember, for a HashSet[A], we need an instance of Equal[A], and we just showed we don’t have an instance of Equal[HashSet[Int]].)
scala> HashSet(HashSet(1, 2, 3, 4, 5))
<console>:22: error: could not find implicit value for parameter A: hasheq.Hash[hasheq.immutable.HashSet[Int]]
HashSet(HashSet(1, 2, 3, 4, 5))
^
But we can have a HashSetoid[HashSet[Int], E], where E is some equivalence on HashSet[Int].
scala> HashSet.of(HashSet(1, 2, 3, 4, 5))
res5: hasheq.immutable.HashSetoid[hasheq.immutable.HashSet[Int],hasheq.immutable.Setoid.ContentEquiv[Int,hasheq.Equality.type]] = HashSetoid(HashSetoid(5, 1, 2, 3, 4))
HashSet.of(elems) is like HashSet(elems), except it tries to infer the equivalence on the element type, instead of requiring it to be equality.
Notice the equivalence tag: Setoid.ContentEquiv[Int, Equality.type].
Its meaning is (again, for humans only) that two setoids are equivalent when they contain the same elements (here, of type Int), as compared by the given equivalence of elements (here, Equality).
The remaining question is: How does this work in the presence of multiple useful equivalences?
Let’s define another equivalence on Int (in addition to the provided equality).
// Our "tag" for equivalence modulo 10.
// This trait will never be instantiated.
sealed trait Mod10
// Provide equivalence tagged by Mod10.
implicit object EqMod10 extends Equiv[Int, Mod10] {
def mod10(i: Int): Int = {
val r = i % 10
if (r < 0) r + 10
else r
}
def equiv(a: Int, b: Int): Boolean = mod10(a) == mod10(b)
}
// Provide hash function compatible with equivalence modulo 10.
// Note that the HashEq typeclass is also tagged by Mod10.
implicit object HashMod10 extends HashEq[Int, Mod10] {
def hash(a: Int): Int = EqMod10.mod10(a)
}
Now let’s create a “setoid of sets of integers”, as before.
scala> HashSet.of(HashSet(1, 2, 3, 4, 5))
res13: hasheq.immutable.HashSetoid[hasheq.immutable.HashSet[Int],hasheq.immutable.Setoid.ContentEquiv[Int,hasheq.Equality.type]] = HashSetoid(HashSetoid(5, 1, 2, 3, 4))
This still works, because HashSet requires an equality on Int, and there is only one in the implicit scope (the newly defined equivalence EqMod10 is not equality).
Let’s try to create a “setoid of setoids of integers”:
scala> HashSet.of(HashSet.of(1, 2, 3, 4, 5))
<console>:24: error: ambiguous implicit values:
both method hashInstance in object int of type => hasheq.Hash[Int]
and object HashMod10 of type HashMod10.type
match expected type hasheq.HashEq[Int,Eq]
HashSet.of(HashSet.of(1, 2, 3, 4, 5))
^
This fails, because there are now more equivalences on Int in scope.
(There are now also multiple hash functions, which is what the error message actually says.)
We need to be more specific:
scala> HashSet.of(HashSet.of[Int, Mod10](1, 2, 3, 4, 5))
res15: hasheq.immutable.HashSetoid[hasheq.immutable.HashSetoid[Int,Mod10],hasheq.immutable.Setoid.ContentEquiv[Int,Mod10]] = HashSetoid(HashSetoid(5, 1, 2, 3, 4))
Finally, does it prevent mixing up equivalences? Let’s see:
scala> val s1 = HashSet(1, 2, 3, 11, 12, 13 )
s1: hasheq.immutable.HashSet[Int] = HashSetoid(1, 13, 2, 12, 3, 11)
scala> val s2 = HashSet( 2, 3, 4, 5, 13, 14)
s2: hasheq.immutable.HashSet[Int] = HashSetoid(5, 14, 13, 2, 3, 4)
scala> val t1 = HashSet.of[Int, Mod10](1, 2, 3, 11, 12, 13 )
t1: hasheq.immutable.HashSetoid[Int,Mod10] = HashSetoid(1, 2, 3)
scala> val t2 = HashSet.of[Int, Mod10]( 2, 3, 4, 5, 13, 14)
t2: hasheq.immutable.HashSetoid[Int,Mod10] = HashSetoid(5, 2, 3, 4)
Combining compatible setoids:
scala> s1 union s2
res16: hasheq.immutable.HashSetoid[Int,hasheq.Equality.type] = HashSetoid(5, 14, 1, 13, 2, 12, 3, 11, 4)
scala> t1 union t2
res17: hasheq.immutable.HashSetoid[Int,Mod10] = HashSetoid(5, 1, 2, 3, 4)
Combining incompatible setoids:
scala> s1 union t2
<console>:26: error: type mismatch;
found : hasheq.immutable.HashSetoid[Int,Mod10]
required: hasheq.immutable.HashSetoid[Int,hasheq.Equality.type]
s1 union t2
^
scala> t1 union s2
<console>:26: error: type mismatch;
found : hasheq.immutable.HashSet[Int]
(which expands to) hasheq.immutable.HashSetoid[Int,hasheq.Equality.type]
required: hasheq.immutable.HashSetoid[Int,Mod10]
t1 union s2
^
We went one step further in the direction of type-safe equivalence in Scala compared to what is typically seen out in the wild today. There is nothing very sophisticated about this encoding. I think the major win is that we can design APIs so that the extra type parameter (the “equivalence tag”) stays unnoticed by the user of the API as long as they only deal with equalities. As soon as the equivalence tag starts requesting our attention (via an ambiguous implicit or a type error), it is likely that the attention is justified.
This article was tested with Scala 2.11.8 and hasheq version 0.3.
