2026-08-31
Doubling.hs
main :: IO ()
main = do
let next = [3, 0, 4, 1, 2] :: [Int]
tables = iterate (\t -> map (t !!) t) next
print (tables !! 2)
これは何を出力するでしょうか?
Answer
Output
[3,0,2,1,4]
next は、状態 i の次の状態を next !! i に置いた表です。map (t !!) t は t の各要素 j を t !! j に置き換えるので、i 番目は t !! (t !! i) で、t を2回たどった先になります。iterate は [next, f next, f (f next), ...] を作るので、tables !! 1 は next を2回、tables !! 2 はその2回分の表をさらに2回たどった、4歩先の表です。
実際に追うと、tables !! 1 は [next !! 3, next !! 0, next !! 4, next !! 1, next !! 2] で [1,3,2,0,4] です。これを u とすると、tables !! 2 は [u !! 1, u !! 3, u !! 2, u !! 0, u !! 4] で [3,0,2,1,4] になります。!! 2 を2回つないだ表と読むと、tables !! 1 の [1,3,2,0,4] と答えてしまいます。段を1つ進めるたびに、足されるのは1歩ではなく、それまでの歩数と同じだけで、歩数は1、2、4と倍になっていきます。next は、0→3→1→0 と回る3状態の輪と、2→4→2 と回る2状態の輪でできています。4歩進むと、3状態の輪では1歩進んだのと同じ位置に、2状態の輪では元の位置に来るので、出力の検算にもなります。