# Equality

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:

- a ~ a. (Reflexivity)
- a ~ b if and only if b ~ a. (Symmetry)
- if a ~ b and b ~ c then a ~ c. (Transitivity)

#### 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$.