浮動小数点数の順序には二種類あるよ（-0.0, +0.0, NaN を比較すると？）

Scala 2.13 がリリースされましたね。
ここで、おもむろに `Seq(3.0, 1.0, 2.0).sorted` などと実行すると、

> warning: object DeprecatedDoubleOrdering in object Ordering is deprecated (since 2.13.0): There are multiple ways to order Doubles (Ordering.Double.TotalOrdering, Ordering.Double.IeeeOrdering). Specify one by using a local import, assigning an implicit val, or passing it explicitly. See the documentation for details.

という警告が出るようになりました。 `Double` の順序型クラスとして `TotalOrdering` `IeeeOrdering` の二つが用意されているので明示的にどちらか一つを選びなさい、と言っていますね。
これは何でしょうか。なぜ順序に種類があるのでしょうか……？

# Java

まずは Java で `Double` の比較について確認してみましょう。

```java
jshell> 1.0 == 1.0               // true
jshell> 1.0 != 1.0               // false
jshell> Double.compare(1.0, 1.0) // 0
jshell> 2.0 > 1.0                // true
jshell> Double.compare(2.0, 1.0) // 1
jshell> 1.0 > 2.0                // false
jshell> Double.compare(1.0, 2.0) // -1
```

それはそう、という感じです。ここに紛れはありません。

それではみんな大好き NaN (Not a Number) を比較してみます。

```java
jshell> 0.0 / 0.0                              // NaN

jshell> Double.NaN == Double.NaN               // false
jshell> Double.NaN != Double.NaN               // true
jshell> Double.compare(Double.NaN, Double.NaN) // 0
jshell> Double.NaN > 0.0                       // false
jshell> Double.compare(Double.NaN, 0.0)        // 1
jshell> 0.0 > Double.NaN                       // false
jshell> Double.compare(0.0, Double.NaN)        // -1
```

おやおや。等号・不等号と `Double.compare` に意見の相違が見られますね？
等号・不等号は `Double.Nan` を食ったらそれはまともな数ではないので `!=` 以外では `false` を吐くと言っています。
対して `Double.compare` は、 `Double.Nan` とは `0.0`よりも大きい数であると言っているのです。

等号・不等号の扱いの方が自然な気もしますが、これが問題になることもあって、

```java
static boolean check(double d1, double d2) {
    return (d1 <= d2) || (d2 <= d1
}
```

という必ず `true` を返すことを期待したい関数が、

```java
jshell> check(1.0, 2.0)        // true
jshell> check(2.0, 1.0)        // true
jshell> check(Double.NaN, 1.0) // false
```

`false` を返してしまうことがあるのですね。こうなるとアルゴリズムによっては、ソートが終わらなかったりします。これはいわゆる全順序律「任意の元 a, b について a ≦ b または b ≦ a」が成り立たない状況です。

対して `Double.compare` は、 

```java
static boolean checkCompare(double d1, double d2) {
    return (Double.compare(d1, d2) <= 0) || (Double.compare(d2, d1) <= 0
}
```

```java
jshell> checkCompare(1.0, 2.0)        // true
jshell> checkCompare(2.0, 1.0)        // true
jshell> checkCompare(Double.NaN, 1.0) // true
```

と `Double.NaN` を含めて全順序律が成り立っています。
※ ちなみに、これは IEEE 754 の totalOrder とは異なるようです。詳しくはコメント欄を読んでください。

この違いはどこから来るのか `Double.compare`の実装を確認してみると、

```java
public static int compare(double d1, double d2) {
    if (d1 < d2)
        return -1;           // Neither val is NaN, thisVal is smaller
    if (d1 > d2)
        return 1;            // Neither val is NaN, thisVal is larger

    // Cannot use doubleToRawLongBits because of possibility of NaNs.
    long thisBits    = Double.doubleToLongBits(d1
    long anotherBits = Double.doubleToLongBits(d2

    return (thisBits == anotherBits ?  0 : // Values are equal
            (thisBits < anotherBits ? -1 : // (-0.0, 0.0) or (!NaN, NaN)
             1)                          // (0.0, -0.0) or (NaN, !NaN)
}
```

[openjdk/jdk/src/java.base/share/classes/java/lang/Double.java](https://github.com/openjdk/jdk/blob/439a48bd1cdaec0337f296102752c4253e1d944c/src/java.base/share/classes/java/lang/Double.java#L1022)

となっていて、なるほどなーというわけですが NaN 以外にも特別な場合がコメントされていますね。こちらも確認してみると、

```java
jshell> -0.0 == +0.0               // true
jshell> -0.0 < +0.0                // false
jshell> Double.compare(-0.0, +0.0) // -1
```

ということで、等号は `-0.0` と `+0.0` が同じ数と言っていますが、 `Double.compare` は`-0.0` より `+0.0` の方が大きい数と言っています。
え、 `-0.0` と `+0.0` を違う数として判定できるの？と驚くかもしれませんが、

```java
jshell> Long.toBinaryString(Double.doubleToLongBits(-0.0)) // 1000000000000000000000000000000000000000000000000000000000000000
jshell> Long.toBinaryString(Double.doubleToLongBits(+0.0)) // 0
```

この通り `-0.0` と `+0.0` は異なるビット表現がされています。

他に `Double` の特殊な値として -∞ を表す `Double.NEGATIVE_INFINITY` と +∞ を表す `Double.POSITIVE_INFINITY` があるので合わせてまとめると、 Java の等号・不等号が定める順序では、

```
-∞ < -1.0 < -0.0 == +0.0 < 1.0 < +∞
```

`Double.compare` が定める順序では、

```
-∞ < -1.0 < -0.0 < +0.0 < 1.0 < +∞ < NaN
```

ということになります。

# Scala

さて、ここまで来れば Scala の方も理解できます。
`TotalOrdering` `IeeeOrdering` の実装を覗いてしまうと、

```scala
trait TotalOrdering extends Ordering[Double] {
  def compare(x: Double, y: Double) = java.lang.Double.compare(x, y)
}
implicit object TotalOrdering extends TotalOrdering
```

```scala
trait IeeeOrdering extends Ordering[Double] {
  def compare(x: Double, y: Double) = java.lang.Double.compare(x, y)

  override def lteq(x: Double, y: Double): Boolean = x <= y
  override def gteq(x: Double, y: Double): Boolean = x >= y
  override def lt(x: Double, y: Double): Boolean = x < y
  override def gt(x: Double, y: Double): Boolean = x > y
  override def equiv(x: Double, y: Double): Boolean = x == y
  override def max[U <: Double](x: U, y: U): U = math.max(x, y).asInstanceOf[U]
  override def min[U <: Double](x: U, y: U): U = math.min(x, y).asInstanceOf[U]
}
implicit object IeeeOrdering extends IeeeOrdering
```

[scala/scala/src/library/scala/math/Ordering.scala](https://github.com/scala/scala/blob/6b4d32c3f518d21a798e8d3cf4a8c35866afa8e2/src/library/scala/math/Ordering.scala#L451)

となっていて `TotalOrdering` はその名の通り Java の `Double.compare` の全順序に従うのですが、 `IeeeOrdering` はメソッドによって異なる順序に従うことが分かります。ややこしいですね。

さて `IeeeOrdering` `TotalOrdering` で挙動がどう異なるか確認してみましょう。

```scala
scala> import Ordering.Double.TotalOrdering
scala> val seq = Seq(+0.0, Double.PositiveInfinity, Double.NaN, -0.0, Double.NegativeInfinity)
scala> seq.sorted
res0: Seq[Double] = List(-Infinity, -0.0, 0.0, Infinity, NaN)
```

```scala
scala> import Ordering.Double.IeeeOrdering
scala> val seq = Seq(+0.0, Double.PositiveInfinity, Double.NaN, -0.0, Double.NegativeInfinity)
scala> seq.sorted
res0: Seq[Double] = List(-Infinity, -0.0, 0.0, Infinity, NaN)
```

おや、同じ結果ですね。
これは `Seq.sorted` が依存しているのは `Ordering.compare` のため `TotalOrdering` も `IeeeOrdering` も同じ順序となるからです。ふーむ。他のメソッドはどうでしょうか。


```scala
scala> import Ordering.Double.TotalOrdering
scala> val seq = Seq(+0.0, Double.PositiveInfinity, Double.NaN, -0.0, Double.NegativeInfinity)
scala> seq.min
res0: Double = -Infinity

scala> seq.max
res1: Double = NaN
```

```scala
scala> import Ordering.Double.IeeeOrdering
scala> val seq = Seq(+0.0, Double.PositiveInfinity, Double.NaN, -0.0, Double.NegativeInfinity)
scala> seq.min
res0: Double = NaN

scala> seq.max
res1: Double = NaN
```

おや、 `min` が違う結果ですね。
これは `Seq.min` が依存しているのは `Ordering.min` のため `TotalOrdering` と `IeeeOrdering` は違う順序となるからです。なるほどなー。

ちなみに `Double` の順序型クラスを明示しなかった場合、Scala 2.13 では `TotalOrdering` 
 と同等のものが参照されますが、Scala 2.13 より前のバージョンで参照されるのは `IeeeOrdering` と同等のものなので、なんと挙動が変わっています。一応、確認してみると、

```scala
// Welcome to Scala 2.12.8 (OpenJDK 64-Bit Server VM, Java 11.0.2).

scala> val seq = Seq(+0.0, Double.PositiveInfinity, Double.NaN, -0.0, Double.NegativeInfinity)
scala> seq.sorted
res0: Seq[Double] = List(-Infinity, -0.0, 0.0, Infinity, NaN)

scala> seq.min
res1: Double = -Infinity

scala> seq.max
res2: Double = -0.0
```

```scala
// Welcome to Scala 2.13.0 (Java HotSpot(TM) 64-Bit Server VM, Java 1.8.0_181).

scala> val seq = Seq(+0.0, Double.PositiveInfinity, Double.NaN, -0.0, Double.NegativeInfinity)
scala> seq.sorted
           ^                                                                      ^
       // warning: object DeprecatedDoubleOrdering in object Ordering is deprecated (since 2.13.0): There are multiple ways to order Doubles (Ordering.Double.TotalOrdering, Ordering.Double.IeeeOrdering). Specify one by using a local import, assigning an implicit val, or passing it explicitly. See the documentation for details.
res0: Seq[Double] = List(-Infinity, -0.0, 0.0, Infinity, NaN)

scala> seq.min
           ^                                                       ^
       // warning: object DeprecatedDoubleOrdering in object Ordering is deprecated (since 2.13.0): There are multiple ways to order Doubles (Ordering.Double.TotalOrdering, Ordering.Double.IeeeOrdering). Specify one by using a local import, assigning an implicit val, or passing it explicitly. See the documentation for details.
res1: Double = -Infinity

scala> seq.max
           ^
       // warning: object DeprecatedDoubleOrdering in object Ordering is deprecated (since 2.13.0): There are multiple ways to order Doubles (Ordering.Double.TotalOrdering, Ordering.Double.IeeeOrdering). Specify one by using a local import, assigning an implicit val, or passing it explicitly. See the documentation for details.
res2: Double = NaN
```

あれ、今度は `max` が違う結果ですね。
これはさらにややこしいことに Scala 2.13 では `Seq.min` `Seq.max` の実装も変更されているためです。
ともかく Scala 2.13 に移行すると挙動が変わる可能性はあるので、 警告が出たら `TotalOrdering` と `IeeeOrdering` のどちらが実装したい機能にふさわしいか考慮したうえで明記するのがいいでしょう。