2026-10-14
CycleOf.hs
cycleOf :: Eq a => (a -> a) -> a -> (Int, Int)
x0 に f を0回、1回、2回と当てていった列 x0, f x0, f (f x0), … に現れる値の種類は有限だとします。この列はいつか前に出た値に戻り、そこから先は同じ並びをくり返します。列の中で、あとでもう一度現れる値のうち最初のものの位置(0から数えます)を μ、その値が次に現れるまでの間隔を λ とします。λ はこの列の周期(period)です。(μ, λ) を返す cycleOf を書いてください。a の値に対して使ってよいのは Eq の比較だけで、f を呼ぶ回数と比較の回数は、どちらも μ + λ の定数倍に収めます。x0 がくり返しの中にあるなら、μ は0です。
入力例 1
cycleOf (\x -> (x * x + 1) `mod` 10) 3
出力例 1
(1,6)
入力例 2
cycleOf (`div` 2) 5
出力例 2
(3,1)
入力例 3
cycleOf id 'a'
出力例 3
(0,1)
Reference
cycleOf :: Eq a => (a -> a) -> a -> (Int, Int)
cycleOf f x0 = (mu, lam)
where
(meet, _) = until (uncurry (==)) (\(t, h) -> (f t, f (f h))) (f x0, f (f x0))
(mu, start, _) = until (\(_, a, b) -> a == b) (\(j, a, b) -> (j + 1, f a, f b)) (0, x0, meet)
lam = 1 + length (takeWhile (/= start) (drop 1 (iterate f start)))
3つの段階で求めます。1段目は、t を f で1歩ずつ、h を2歩ずつ進め、両者が等しくなるまで until で回します。i 歩目で等しくなったなら、列の i 番目と 2i 番目が同じ値です。i 番目の値があとでもう一度現れたので i は μ 以上で、くり返しの中で i 個先が同じ値なので、i は λ の倍数です。
2段目は、a を x0 から、b を1段目で出会った値から、同時に1歩ずつ進めます。j 歩目の a は列の j 番目、b は i + j 番目です。j が μ より小さいうちは、a の値はあとに二度と現れないので、b と等しくなることはありません。j が μ になると、i が λ の倍数なので2つは同じ値を指します。最初に等しくなった j が μ で、そのときの値がくり返しの始まりです。3段目で、その値から1歩ずつ進めて同じ値に戻るまでの歩数を数えれば λ になります。
どの段階も、進めた歩数は μ + λ の定数倍で済みます。これまでに出た値をリストに覚えて elem で探す書き方では、== の回数が (μ + λ) の2乗に比例し、Eq だけでは Data.Map のような探索の速い表も使えません。1段目の、速さの違う2つの位置を走らせる方法はフロイドの循環検出法(Floyd's cycle-finding algorithm)と呼ばれ、ウサギとカメのアルゴリズムともいいます。
掲載したのは参考実装で、唯一の正解ではありません。until の代わりに where の中で再帰する補助関数を書いても、同じ3段階になります。