Namaran

Code daily. Without assist.

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。

  1. Haskell 2010 の報告書は Eq に法則を定めていませんが、GHC の base の文書は、x == y なら f x == f y となること(Extensionality)を、インスタンスが満たすよう勧める性質の1つに挙げています。== を状態の一部だけの比較にすると、elem や lookup のように == を「同じ値」の意味で使う関数すべての前提が崩れます。位置だけを比べたいなら、samePlace のような別の名前の関数にします。