2026-11-15
Kahan.hs
kahan :: [Double] -> Double
kahan = fst . foldl step (0, 0)
where
step (s, c) x = (t, c)
where
y = x - c
t = s + y
c = (t - s) - y
main :: IO ()
main = print (kahan (replicate 10 0.1))
kahan は、足し算で丸められて失われた分を c に覚えておき、次の値から差し引くことで、総和の誤差を抑えるつもりの関数です。kahan (replicate 10 0.1) は 1.0 を出力するはずが、いまは何も出力せず、<<loop>> という例外で止まります。
Answer
Wrong
step (s, c) x = (t, c)
where
y = x - c
t = s + y
c = (t - s) - y
where の束縛は再帰的で、その中で定義した名前は、where のすべての式から見えます。c = (t - s) - y で定義した c は、引数のパターンで受け取った c を隠すので、y = x - c の c も新しい c を指します。手続き型の言語で c を上書きする書き方をそのまま写すと、こうなります。
新しい c を求めるには t と y が要り、t は y から、y は新しい c から求めます。値が自分自身を待つ形になり、最初に結果を表示しようとしたとき、GHC の実行時システムがこの循環を見つけて <<loop>> を投げます。
Right
step (s, c) x = (t, c')
where
y = x - c
t = s + y
c' = (t - s) - y
新しい補正値に c' という別の名前を付けます。y = x - c の c は、前の要素までに失われた分を持つ引数の c を指すようになり、循環は消えます。0.1 を10回そのまま足すと 0.9999999999999999 になりますが、この関数は失われた分を次の足し算で取り戻すので、1.0 を返します。1
- GHC の
-Wallは、引数の名前をwhereで隠すと-Wname-shadowingで警告します。<<loop>>を見つけられるのは実行時システムが循環に気付いたときだけで、気付かなければプログラムは止まらずに待ち続けます。