起
「すごい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 を見てみる。
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
For
Float
andDouble
, the semantics of the enumFrom family is given by the rules forInt
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から numericEnumFromThenTo
のソース を見る。
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.5 / 2 = 2.25$ 以下なので結果に含まれた。
結
冒頭の引用を再び示す。
レンジに関する最後の注意。浮動小数点数に使うときは気をつけて! 浮動小
数点数は精度に限りがあるので、レンジで使うと次のようなおかしな振る舞いを
することがあります。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 の配慮が裏目に出た結果。不都合なことは既知であるがバクでなく仕様
だった。
ずっと引っかかっていた謎が解けてすっきりしました。