2026-10-14
Bounce.hs
data Ball = Ball Int Int
instance Eq Ball where
Ball p _ == Ball q _ = p == q
bounce :: Ball -> Ball
bounce (Ball p v)
| p + v < 0 || p + v > 3 = Ball (p - v) (-v)
| otherwise = Ball (p + v) v
period :: Eq a => (a -> a) -> a -> Int
period f x0 = 1 + length (takeWhile (/= meet) (drop 1 (iterate f meet)))
where
(meet, _) = until (uncurry (==)) (\(t, h) -> (f t, f (f h))) (f x0, f (f x0))
main :: IO ()
main = print (period bounce (Ball 0 1))
period f x0 は、x0 に f を0回、1回、2回と当てていった列がやがて同じ並びのくり返しに入るとき、そのくり返し1周の長さ、つまり列の周期(period)を返す関数です。Ball p v は0から3までの範囲を位置 p、速度 v で動き、範囲を出そうになると向きを変えて跳ね返る玉で、bounce がその1歩です。period bounce (Ball 0 1) を実行すると、いまは 2 と出力されます。本来の出力は 6 です。
Answer
Wrong
data Ball = Ball Int Int
instance Eq Ball where
Ball p _ == Ball q _ = p == q
Ball の状態は位置と速度の組なのに、この == は位置しか比べません。period は、等しい値からは同じ列が続く、つまり x == y なら f x == f y であることを前提にしていますが、位置2の玉は、上りの Ball 2 1 なら次に3へ、下りの Ball 2 (-1) なら次に1へ進むので、「等しい」2つの値から違う列が続いてしまいます。
列の状態は Ball 0 1, Ball 1 1, Ball 2 1, Ball 3 1, Ball 2 (-1), Ball 1 (-1), Ball 0 (-1), Ball 1 1, … と進みます。until は2歩目で、1歩ずつ進む側の Ball 2 1 と2歩ずつ進む側の Ball 2 (-1) を等しいと判定して止まり、meet から進めた列も2歩先の Ball 2 (-1) で止まるので、2が返ります。位置の並び 0, 1, 2, 3, 2, 1 は6ごとにくり返しますが、1周の中に位置2が上りと下りで2度現れるため、位置だけで比べると周期の途中で止まります。
Right
data Ball = Ball Int Int deriving Eq
deriving Eq で作られる == は、位置と速度の両方を比べます。状態が丸ごと一致したときだけ等しくなるので、等しい値からは必ず同じ列が続きます。最初の Ball 0 1 は二度と現れず、Ball 1 1 から Ball 0 (-1) までの6つの状態がくり返します。until は6歩目の Ball 0 (-1) で止まり、そこから1周して戻るまでの6が返ります1。
- Haskell 2010 の報告書は
Eqに法則を定めていませんが、GHC のbaseの文書は、x == yならf x == f yとなること(Extensionality)を、インスタンスが満たすよう勧める性質の1つに挙げています。==を状態の一部だけの比較にすると、elemやlookupのように==を「同じ値」の意味で使う関数すべての前提が崩れます。位置だけを比べたいなら、samePlaceのような別の名前の関数にします。