下記のような感じでhugsの上で動作確認しつつ小さな関数をくみ上げて実装。
f :: Int -> Int
f n
| n == 1 = 1
| even n = f (n `div` 2)
| otherwise = f (3 * n + 1)
f2 :: (Int,Int) -> (Int,Int)
f2 (n,k)
| n == 1 = (n,k)
| even n = f2 (n `div` 2, k + 1)
| otherwise = f2 (3 * n + 1, k + 1)
g :: Int -> Int
g n = snd ( f2 (n, 1))
g2 :: Int -> (Int,Int)
g2 n = (n, g n)
gs :: Int -> [(Int,Int)]
gs n = map g2 [1 .. n]
h2 :: [(Int,Int)] -> (Int,Int) -> (Int,Int)
h2 [] m = m
h2 (x:xs) m = case (snd x > snd m) of
True -> h2 xs x
False -> h2 xs m
h :: Int -> Int
h n = fst (h2 (gs n) (0,0))
main = do args <- getArgs
mapM_ (putStrLn . show . h . read) args
これをhugsの上でテスト。
Main> g2 3
(3,8)
Main> gs 10
[(1,1),(2,2),(3,8),(4,3),(5,6),(6,9),(7,17),(8,4),(9,20),(10,7)]
Main> h2 $$ (0,0)
(9,20)
Main> h 10
9
Main>
ghcでコンパイルして、iBook G4 で実行して時間測定。
% /usr/bin/time ./collatz 100
97
0.07 real 0.00 user 0.01 sys
% /usr/bin/time ./collatz 1000
871
0.18 real 0.10 user 0.01 sys
% /usr/bin/time ./collatz 10000
6171
1.28 real 1.13 user 0.04 sys
% /usr/bin/time ./collatz 100000
77031
14.64 real 13.78 user 0.28 sys
---
7/12追記
はてなのHaskellグループでみつけた回答→collatz予想 @ haskellのある暮らし
うーむ、奇麗なコードだ。あと、明示的にHashとかを使ってメモ化すると早い、ということの様だ。
遅延評価で再計算しないはずだと考えると、明示的にメモ化するメリットはどこにあるのだろうか。検索性能？
