Hatena::Grouphaskell

猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 このページをアンテナに追加 RSSフィード

2012-01-25

第9章 対話プログラム #3

22:47 |  第9章 対話プログラム #3 - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

ライフゲーム

さて、9.7はライフゲームの実装。

ひたすら写経。9.5で実装した関数群を使っている。

module NineSeven where

import NineFive

width :: Int
width =  5

height :: Int
height =  5

type Board = [Pos]

glider :: Board
glider =  [(4,2), (2,3), (4,3), (3,4), (4,4)]

showcells   :: Board -> IO ()
showcells b =  seqn [writeat p "O" | p <- b]

isAlive     :: Board -> Pos -> Bool
isAlive b p =  elem p b

isEmpty     :: Board -> Pos -> Bool
isEmpty b p =  not (isAlive b p)

neighbs       :: Pos -> [Pos]
neighbs (x,y) = map wrap [(x-1,y-1), (x,y-1), (x+1,y-1),
                          (x-1,y),            (x+1,y),
                          (x-1,y+1), (x,y+1), (x+1,y+1)]

wrap       :: Pos -> Pos
wrap (x,y) =  (((x-1) `mod` width) + 1, ((y-1) `mod` height) + 1)

liveneighbs   :: Board -> Pos -> Int
liveneighbs b =  length . filter (isAlive b) . neighbs

survivors   :: Board -> [Pos]
survivors b =  [p | p <- b, elem (liveneighbs b p) [2,3]]

births   :: Board -> [Pos]
births b =  [p | p <- rmdups (concat (map neighbs b)),
                 isEmpty b p,
                 liveneighbs b p == 3]

rmdups        :: Eq a => [a] -> [a]
rmdups []     =  []
rmdups (x:xs) =  x:rmdups (filter ((/=) x) xs)

nextgen   :: Board -> Board
nextgen b =  survivors b ++ births b

life   :: Board -> IO ()
life b =  do cls
             showcells b
             wait 5000
             life (nextgen b)

wait   :: Int -> IO ()
wait n =  seqn [return () | _ <- [1..n]]

life gliderって実行すると、たしかにグライダーが!

ただし無限ループするので、Ctrl-cで止めないといけないけど。

waitがビジーループなのがおもしろい。IOモナドにもだいぶん馴染んできたかな。

木探索とCPS

23:10 | 木探索とCPS - 猫とC#について書く代わりにHaskellとF#について書くmatarilloの日記 のブックマークコメント

もともと、俺のHaskell学習の目標は、“ Haskellと確率と限定継続 - Life Goes Onを全部理解できるようになること”だったわけで、それは今でも変わっていない。

で、Haskellはだんだんわかって来たけど、“木探索から CPS にすることで効率化”が腑に落ちてなかった。

そんな時にお気楽 OCaml プログラミング入門というページを見つけた。

おお、なるほどね。CPSで効率化を理解する取っ掛かりができたぞ。

rst76rst762012/03/01 23:131ヶ月遅れのコメントすみません。リンク先にもある通り、“木探索から CPS にすることで効率化”というのは間違いです。同じ計算をするなら、CPSにしようがしまいが、コストは変わりません。
確率計算の例だと、CPSに変換する際に実は計算モデルも若干変わっていて、そのために効率化されています。逆にもともとの木探索でも、モデルの記述をちょっと変えるだけで効率化できます。木探索が悪いわけではなくて、モデルの記述の仕方が悪いのです。
そのあたりは僕も整理できてなくて、うやむやにしていたのですが、時間を見つけて考えたいと思います。(そういう意味ではオリジナルの論文も、誤りがあるのではないかと思っています)

matarillomatarillo2012/03/02 01:21実は、木探索とモナドにもっと慣れたらあらためてまた考えようと思って、ほっといてあります。;-)