Proposal
I think we should add typeclasses for equality and hashing to the Scala ecosystem - either to the Scala Platform, or to the Scala library itself.
Motivation
Equality
Equality testing (==
) uses universal equality, which enables comparing completely different types that can never be equal, and can only lead to bugs. Additionally, in order to have numbers behave someone sensibly, ==
implements cooperative equality; this leads to many problems, one of which is significantly reduced performance (see Can we get rid of cooperative equality?).
It would be very helpful to have a type-safe way of testing for equality, to help reduce bugs and improve code correctness. On top of this, because an equality typeclass doesnât allow comparing different types, the cause for cooperative equality doesnât ever arise, and it is a complication that can be skipped.
Hashing
Hashing uses AnyRef.hashCode():Int
, which has a number of problems. It makes it difficult to implement hashing strategies other than Javaâs default, as all the hash data about the object is already âmixedâ before it is returned. Even if you create a hashing strategy which returns 256 bits, you can only get 32 bits of hash data out of any object, so the object will not be hashed as thoroughly as you wish (this is a major problem for cryptographic hashing). On top of this, if you want to hash just a single object into more than 32 bits, there is no good way to do so - you only have 32 bits of information to work with.
Instead of a method which returns a fixed amount of data for a hash, it would be better to have a typeclass which defines how the object gets mixed into some hash state. Then, you can implement your own hashing strategy, and the hash typeclass will properly mix all of the objectâs data into your hash state. This allows even cryptographic hashing over objects, without resorting to roundabout methods (e.g. turning the object into JSON and hashing that).
Existing Libraries
Why do we need this, if there are already several libraries - such as scalaz and cats - with equality typeclasses?
Unfortunately, scalaz does not include a typeclass for hashing, and the one in cats only returns Int
s. Additionally, both libraries include lots of other code, which you might not want to depend on if all you want is equality and hashing (arguably, cats kernel doesnât have too much extra, but it does have stuff for monoids and semigroups and other things). cats does not have implicit operators for typeclass equality either (at least not that I could find), which is important for making type-safe equality usable.
Strawman Implementation
Iâve created a strawman implementation to test the semantics and usability. The design for hashing is significantly inspired by Rustâs std::hash
.
trait Eql[T] {
def equal(x: T, y: T): Boolean
def notEqual(x: T, y: T): Boolean = !equal(x, y)
}
trait Hash[T] {
def hash(value: T, state: HashState): Unit
}
trait Hasher[R] {
def state: HashState
def reset(): Unit
def result(): R
final def +=[T](t: T)(implicit hash: Hash[T]): this.type = {
hash.hash(t, state)
this
}
}
trait HashState {
def +=(byte: Byte): this.type
def +=(int: Int): this.type
def +=(long: Long): this.type
def +=(bytes: Array[Byte]): this.type
}
trait HashFactory[R, H <: Hasher[R]] {
def newHasher: H
def hash[T: Hash](value: T): R = (newHasher += value).result()
}
implicit final class RichAnyEql[A](val self: A) extends AnyVal {
def ===(that: A)(implicit eql: Eql[A]): Boolean = eql.equal(self, that)
def =!=(that: A)(implicit eql: Eql[A]): Boolean = eql.notEqual(self, that)
}
The full code is on GitHub.