読者です 読者をやめる 読者になる 読者になる

bonar note

京都のエンジニア bonar の技術的なことや技術的でない日常のブログです。

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先生のトラックバックに期待です。

まとめ

Haskell まだまだ入門以前ですが、すごい新鮮ですね。答えを求める関数を書く、っていうよりは、答えが求まるような世界のルールを書く、って感じがしました。純粋な数値計算以外のものをどうやって実装していくのかまだイメージ出来ないですが、少しずつ楽しみながらやって行きたいなと思いました。