# Equality

Last modified on August 21, 2018 by Alex

Scala’s default equality == is a complete disaster. It is neither reflexive, symmetric, transitive, nor does it satisfy congruence or extensionality laws. It is inconsistent with equals. It does not respect types, allowing you to compare completely unrelated types.

Basically, it does not satisfy any laws at all.

### Comparing unrelated types?

Let’s start with the fact that == allows you to compare unrelated types:

1 == 1L // true
(1.0, BigInt(1)) == ((1, 1.0)) // true

It is not necessarily a bad thing on its own. However, it interacts badly with non-parametric top type and cooperative equality.

#### Cooperative equality

Scala has to do extra work for generic parameters or abstract types deriving from Any due to implicit widening of numerical types and cooperative equality: a == b calls BoxesRunTime.equals, which results in observable performance losses.

If cooperative equality were to be removed, it would result in rather bizzare behavior of type ascription:

0 == 0L // true
(0 : Any) == (0L : Any) // true, but will be false if cooperative equality is removed

And speaking of bizzare behavior due to type ascription, null can be ascribed to Int, which leads to a number of puzzlers:

(null : java.lang.Integer) == 0 // false
((null : java.lang.Integer) : Int) == 0 // true
((null, 1) : (java.lang.Integer, Int)) == ((0, 1)) // false

Another consequence of cooperative equality is that Scala’s hash code method ## is different from Java’s hashCode:

scala> val p = new java.lang.Float(1)
p: Float = 1.0

scala> p.hashCode
res0: Int = 1065353216

scala> p.##
res1: Int = 1

Implicit numerical widening makes == incompatible with equals even though it uses equals in its implementation for reference types:

0 == 0L // true
0 equals 0L // false
(0 : Any) == (0L : Any) // true, but might become false in the future.
(0 : Any) equals (0L : Any) // false

A slightly different example of incompatibility with equals that relies on IEEE 754 instead:

val nan0 = java.lang.Double.longBitsToDouble(0x7ff8000000000000L)
val nan1 = java.lang.Double.longBitsToDouble(0x7ff8000000000001L)

nan0 == nan0 // false
nan0.equals(nan0) // true
nan0.compare(nan0) // 0

nan0 == nan1 // false
nan0.equals(nan1) // true
nan0.compare(nan1) // 0

IEEE 754 is a widely used technical standard for floating-point computation. The standard defines binary formats, rounding rules, and floating-point operations. Unfortunately, most major languages (but not Rust) adopted IEEE 754 equality as the implementation for == on floating-point types, which leads to all sorts of peculiar behavior (including side-effects).

In mathematics, equality is an equivalence relation, which means that it has to satisfy three axioms:

#### Is Scala’s == equality?

No. It is not reflexive:

nan0 == nan0 // false

And it is not transitive:

9007199254740992L == 9007199254740992.0 // true
9007199254740992.0 == 9007199254740993L //true
9007199254740992L == 9007199254740993L // false

123456789.toFloat // 1.23456792E8
123456789.toFloat == 123456789 // true
123456789 == 123456789.toFloat // true
123456788 == 123456789.toFloat // false
123456790 == 123456789.toFloat // true

Furthermore, since it relies on equals for reference types, there are probably some non-symmetric equals in the wild as well.

Another desirable quality of equality is congruence with respect to the chosen subset of the language. In practice this means that if a equals to b, then f(a) should be equal to f(b) for any f : A => Boolean that can be implemented using only features from a certain subset of the language features.

Scala’s == is not congruent even with respect to Scalazzi, a limited subset of the language:

-0.0d == 0.0d // true
def f(x: Double): Double = 1 / x
f(-0.0d) == f(0.0d) // false

And it is definitely not congruent with respect to the entirety of Scala, due to a number of non-parametric methods:

val a: Option[Int] = Some(1)
val b: Option[Int] = Some(1)
a == b // true
def f(x: Option[Int]): Boolean = x eq a
f(a) == f(b) // false

The opposite of congruence is extensionality, which means that if f(a) == f(b) for every choice of f : A => Boolean in some subset of the language, then a must be equal to b.

Even extensionality is somewhat broken because == is universal:

val a: Int => Int = x => x + 1
val b: Int => Int = x => x + 1

// quite obviously, f(a) == f(b) for all f
// caveat: f should not refer to a and b directly
a == b // false

This leads us to the next point

#### Universal equality

Scala’s == is defined on all types, including functions, mutable types such as Array[Int], and infinite streams, which makes == both impure and potentially non-terminating.

Are there any arguments against a universal Eq defined only on finite immutable types? You could preserve parametricity by explicitly asking for an Eq instance. Instances could potentially be automatically derived by the compiler (with some important caveats for quotient types).

I don’t see problems with function equality, as long as it’s structural, e.g. _ + 1 and a => a + 1 are the same functions but 2017-04-26T22:22:08.573Z I am okay with any normalization… :P It will be brittle, but it will work 2017-04-26T22:22:16.072Z Just hash the bytecode 2017-04-26T22:22:32.109Z recursively. deal with recursion separately 2017-04-26T22:22:35.398Z yeah 2017-04-26T22:22:41.735Z basically :P 2017-04-26T22:22:51.226Z mutual recursion can still be handled 2017-04-26T22:23:11.251Z and self-recursion 2017-04-26T22:23:59.873Z (not for strong normalization obviously) 2017-04-26T22:24:11.399Z functions are static 2017-04-26T22:24:37.015Z so it’s a small constant for every function object that you have 2017-04-26T22:25:19.819Z Hmm yeah I guess there is a problem with closures… hash the closure and Eq what it closed over 2017-04-26T22:27:23.052Z Open recursion is overrated anyway, I’d rather have only functions $\in \Sigma_0$.