浮動小数点数のレンジ、あるいは enumFromThenTo

# 起

「すごいHaskell楽しく学ぼう！」 §1.4 レンジでチン！ の最後に、次のように書いてある。

> レンジに関する最後の注意。浮動小数点数に使うときは気をつけて！ 浮動小
> 数点数は精度に限りがあるので、レンジで使うと次のようなおかしな振る舞いを
> することがあります。
> ```
> ghci> [0.1, 0.3 .. 1]
> [0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]
> ```

浮動小数点数の仕組みと10進小数の相性の悪さから、`0.1 + 0.2` が `0.30000000000000004` になってしまう計算誤差があるのは仕方ない。
そこを大目にみて、上の結果を

```
ghci> [0.1, 0.3 .. 1]
[0.1,0.3,0.5,0.7,0.9,1.1]
```

とみなしても、まだ何かおかしい。終了する値には 1 を指定しているのに、1をはるかに越えた 1.1 までが出てきている。計算精度の問題ってレベルじゃねーぞ！

もっと酷い例だと、整数相当でも奇妙な動作をする。

```
ghci> [6, 8 .. 5] :: [Int]
[]
ghci> [6, 8 .. 5] :: [Double]
[6.0]
```

# 承

レンジは `Prelude` にある `Enum` 型クラスのメソッド `enumFromThenTo` に皮をかぶせたもの。これの hackage を見てみる。

[hackage](https://hackage.haskell.org/package/base-4.19.1.0/docs/Prelude.html#t:Double)

> List generators have extremely peculiar behavior, mandated by Haskell Report 2010:
>
> ```
> >>> [0..1.5]
> [0.0,1.0,2.0]
> ```

「チョー変な動きするけど、それは Haskell Report 2010 に書いてあるとおりだから！」

## 仕様

Haskell Report 2010 の記述を探す。
[Haskell 2010 Report - 3.4 The Enum Class](https://www.haskell.org/onlinereport/haskell2010/haskellch6.html#x13-1310006.3.4)

> For `Float` and `Double`, the semantics of the enumFrom family is given by the rules for `Int` above, except that the list terminates when the elements become greater than $e_3 + i∕2$ for positive increment $i$, or when they become less than $e_3 + i∕2$ for negative $i$.

終了するのは、終了値 $e_3$ を越えたときでなく、さらに増分 $i$ の半分を超えたとき、とある。

## 実装

上のhackageからでは情報が出てこないので、[hackage GHC.Enum](https://hackage.haskell.org/package/base-4.19.1.0/docs/GHC-Enum.html)から `numericEnumFromThenTo` の[ソース](https://hackage.haskell.org/package/base-4.19.1.0/docs/src/GHC.Real.html#numericEnumFromThenTo) を見る。

```haskell
numericEnumFromThenTo e1 e2 e3 =
    takeWhile predicate (numericEnumFromThen e1 e2)
  where
    mid = (e2 - e1) / 2
    predicate | e2 >= e1  = (<= e3 + mid)
              | otherwise = (>= e3 + mid)
```

確かに、Haskell Report の記述どおり。

## 考察

では、どうしてこんな定義になっているのだろうか。

浮動小数点数では、計算誤差のために、指定した値ぴったりにはなかなかならない。
例えば `0.1 + 0.2 = 0.30000000000000004 > 0.3` なので

```
ghci> takeWhile (0.3 >=) $ iterate (0.2 +) 0.1
[0.1]
```

となって上限0.3を内部的に越えてしまう。これが計算精度の問題。
これを回避するために、終値 $e_3$ よりも少し、誤差を吸収できるだけ余裕を持たせた値 $e_3 + \delta$ を終了の基準にする必要がある。$\delta$ をいくつにするのがよいか。$0.1 \ i$ などの定数を使うのは、根拠が不十分である。
最大限の誤差を受け止められる設定として、$e_3$ からさらに1ステップ進めた $e_3 + i$ との中間点 $e_3 + i / 2$ にすることは、もっともらしい。

```
ghci> [0.1, 0.1 + 0.2 .. 0.3]
[0.1,0.30000000000000004]
```

# 転

終了の基準を $e_3 + i / 2$ にして誤差を最大限受け止める、という設計は、$e_3$ が通過予定の値、つまり $e_3 - e_1 = k \  (e_2 - e_1)$ （$k$は整数）のときは妥当である。

ところが逆に、$k$ が整数 $+ 0.5$ になるような、数列が終了基準点をちょうど通るような値が $e_3$ に指定されると、この設計が裏目に出る。
誤差のために終了基準点をわずかに下回った値が、打ち切られずに通過してしまう。

```
ghci> [0.1, 0.3 .. 1]
[0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]
```

終了基準 1.1 をわずかに下回った 1.0999999999999999 は、終値 1 をはるかに越える値にもかかわらず結果に紛れ込んだ。

```
ghci> [6, 8 .. 5] :: [Double]
[6.0]
```

終了基準 6 を上回ってはいない 6 は、終値 5 をはるかに越える値にもかかわらず結果に紛れ込んだ。

```
ghc> [0 .. 1.5]
> [0.0,1.0,2.0]
```

終値 1.5 をはるかに越える 2.0 は、終了基準 $1.5 + 1.0 / 2 = 2.0$ 以下なので結果に含まれた。

# 結

冒頭の引用を再び示す。

> レンジに関する最後の注意。浮動小数点数に使うときは気をつけて！ 浮動小
> 数点数は精度に限りがあるので、レンジで使うと次のようなおかしな振る舞いを
> することがあります。
> ```
> ghci> [0.1, 0.3 .. 1]
> [0.1,0.3,0.5,0.7,0.8999999999999999,1.0999999999999999]
> ```

この「おかしな振る舞い」のうち、

- 0.9 でない 0.8999999999999999 が出てくる原因は、浮動小数点数の精度
- 終値 1 をはるかに越える値 1.0999999999999999 が結果に紛れ込む理由は、浮動小数点数の精度を考慮して、それでもなるべく意図通りに動作するようにという Haskell Report 2010 の配慮が裏目に出た結果。不都合なことは既知であるがバクでなく仕様

だった。

ずっと引っかかっていた謎が解けてすっきりしました。