[Haskell] LL Ring : Round 2

LL Ringの、キミならどう書く 2.0 - ROUND 2 -をHaskellで解いてみた ... 特に工夫した訳ではないので単に解いただけに過ぎないのではあるが。

下記のような感じで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とかを使ってメモ化すると早い、ということの様だ。
遅延評価で再計算しないはずだと考えると、明示的にメモ化するメリットはどこにあるのだろうか。検索性能？