Haskell 勉強会第一回の復習(3n+1問題)
社内でゲリラ的にHaskell勉強会が行われたので、忘れないうちに少し書いてみようと思います。
本当に障りしかやってないので勘違いしてる可能性も大なのですが、有名な数論の未解決問題であるウラムの問題（3n+1問題）の計算をしてみたいと思います。
3n + 1
規則は簡単で、
- ある自然数nが偶数の場合は2で割る
- 奇数の場合は3倍して1を足す
これを繰り返すといずれすべての自然数は1に収束するという予想です。以下のように書いてみたのですが、
even :: Int -> Bool even n = if (n `mod` 2) == 0 then True else False ulam :: Int -> Int ulam n | n == 1 = 1 | (even n) == True = ulam $ n `div` 2 | (even n) == False = ulam $ (n * 3) + 1
実行すると偶数判定の関数evenで「それもうすでにあるよ」というエラー（単純に名前かぶってるだけですが）が。。
<interactive>:1:0:
Ambiguous occurrence `even'
It could refer to either `Main.even', defined at ulam.hs:3:0
or `Prelude.even', imported from Prelude言われた通り Prelude.even を使って書き直してみると、、、
bash-3.2$ ghci ulam.hs GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Main ( ulam.hs, interpreted ) Ok, modules loaded: Main. *Main> ulam 5 1 *Main> ulam 497 1 *Main> ulam 384932 1 *Main>
できたっぽい！全部 1 になってるし！
でもこれだと本当にできてるのかちょっと不安。。かといって、途中に putStrLn とかを挟んで途中経過を見ようとすると期待される結果の型が変わってしまうのでうまく出来ず。。どうしようとフンフン調べてみると、Debug.Trace を使うとうまい事できるっぽい。
http://itpro.nikkeibp.co.jp/article/COLUMN/20071204/288630/?ST=develop&P=2
import Prelude import Debug.Trace ulam :: Int -> Int ulam n | n == 1 = 1 | (even n) == True = trace (show n) $ ulam $ n `div` 2 | (even n) == False = trace (show n) $ ulam $ (n * 3) + 1
上記に書き換えて実行すると、
bash-3.2$ ghci ulam.hs GHCi, version 6.10.1: http://www.haskell.org/ghc/ :? for help Loading package ghc-prim ... linking ... done. Loading package integer ... linking ... done. Loading package base ... linking ... done. [1 of 1] Compiling Main ( ulam.hs, interpreted ) Ok, modules loaded: Main. *Main> *Main> *Main> ulam 15 15 46 23 70 35 106 53 160 80 40 20 10 5 16 8 4 2 1
うまいこといってるっぽい！嬉しい！
あとはすべての自然数に関して上記が成り立つ事を証明するコードを追加すればノーベル数学賞間違いなしですね。いい実装を思いついたのですが余白が足りないので、id:tom-lpsd先生のトラックバックに期待です。
