Hatena::ブログ(Diary)

Hatena’s Kitchen RSSフィード

2009-04-07 Haskell勉強会

Haskell勉強会 #1

| 01:12 |  Haskell勉強会 #1 - Hatena’s Kitchen を含むブックマーク

誠に恐縮なのですが、チームリーダがチャンスをくれたので、社内でHaskell勉強会なるものをやらせていただきました。

人に教えるのは、苦手分野だと自覚しつつも特攻し、見事撃沈しました。参加者のみなさま期待に添えず申し訳ありませんでした。

結局人に教えることができないということは、自分が理解していないということなので、まだまだ勉強不足ということを実感しました。

と、反省ばかり残る勉強会だったわけですが、bonarさんが興味をしめしてくださったので、僕なりの書き方を紹介しようと思います。

お題は、ウラムの問題(3n+1問題)です。(恥ずかしながらこういう問題があることすら知りませんでした。。。)

ulam :: Integer -> [Integer]
ulam 1 = 1:[]
ulam n | even n = n:(ulam $ n `div` 2)
ulam n = n:(ulam $ n * 3 + 1)

bonarさんは、Debug.Traceを駆使して、収束の過程をのぞいていますが、そもそも数列全体を俯瞰したいのであれば、数列を返す関数にしてしまうのがてっとり早いと思います。と、いうわけで上のコードになりました。コード本質は、bonarさんが書かれているものと変わらないので、重箱のすみをつつくような指摘で恐縮です。。

これを実行してみると

tom-macbook ~ $ ghci ulam.hs
GHCi, version 6.10.2: 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 6
[6,3,10,5,16,8,4,2,1]

と、1に収束していく様子を見ることができます。

僕は頭が悪いので、良い証明は思いつかないのですが、以下のコード無限に走らせつづければ、いつか反例が見つかるかもしれません。

Main> filter (/=1) $  map (last . ulam) [1..]

本当は、この例でQuickCheckとかを使ったテストを紹介したかったのですが、諸事情によりほろ酔い状態なので、

まじめな話は次回書くことにします。

tom-lpsdtom-lpsd 2009/04/08 01:20 って、本当に反例があった場合は収束しないので last が返ってこなくて、正しくても間違ってても無限ループするという、、、ダメダメですね orz

const ()const () 2009/04/08 19:02 ulam n = (++[1]) $ takeWhile (/=1) $ iterate f n where
 f n = if even n then n `div` 2 else n * 3 + 1
という手も。

tom-lpsdtom-lpsd 2009/04/08 21:39 > const ()さん
なるほどー、iterate!
無限リストにしてtakeWhile、なかなかかっこいいですね。

スパム対策のためのダミーです。もし見えても何も入力しないでください
ゲスト


画像認証