2026-08-31
Jump.hs
step :: Int -> Int
step x = (x * x + 1) `mod` 1000
main :: IO ()
main = print ((iterate (\g -> g . g) step !! 40) 2)
0〜999 の値を step で次の値へ進める処理を、2から始めて240 回繰り返した結果を、回数を倍々にしていく方法で速く求めるつもりのプログラムです。いまは何も表示されないまま終わりません。本来は 330 がすぐに表示されます。
Answer
Wrong
main = print ((iterate (\g -> g . g) step !! 40) 2)
iterate (\g -> g . g) step の j 番目は、step を2j 回合成した関数で、意味の上では正しく240 回先を表しています。しかし g . g は「g を呼んでから、もう一度 g を呼ぶ」という関数を作るだけで、g の結果を前もって計算してはおきません。40段目の関数を2に適用すると、39段目の関数が2回呼ばれ、それぞれが38段目を2回呼び、と枝分かれして、最後に step そのものが240 回、約1.1兆回呼ばれます。回数を倍にする表を作ったつもりでも、手間は1回ずつ進めるのと変わりません。
Right
import Data.Array
memo :: (Int -> Int) -> Int -> Int
memo g = (table !)
where
table = listArray (0, 999) (map g [0 .. 999])
main :: IO ()
main = print ((iterate (\g -> memo (g . g)) step !! 40) 2)
値は0〜999の1000通りしかないので、各段の関数を、すべての値に対する結果を並べた配列に書き出します。memo g が返すのは配列 table を引く関数で、table の各要素は g を呼ぶ計算として遅延されたまま置かれ、最初に引かれたときに一度だけ計算されて、その後は結果が共有されます。次の段の g . g が呼ぶ g は前の段の配列を引く関数なので、1回の呼び出しは配列を2回引くだけです。各段で計算する要素は高々1000個、40段で4万回ほどで済みます。配列に使う Data.Array は、Haskell 2010 の報告書に含まれる標準のライブラリです。