Haskellのモナド２(3)

リストモナドの計算（型[a]で終わるもの）は「０個以上の値が結果となる計算」を表しています。例えば、三目並べをモデリングしているとします。ちょっとだけわざとらしいのですが、ここではゲームが進行する可能性のある状態を見つけることを問題とします。つまり、与えられたボードの状態から、派生する状態を３つ先のターンまで求めるということです。
リストモナドのインスタンス定義は以下のようになります。

instance Monad [] where
	return a = [a]
	xs >>= f = concat (map f xs)

モナドは計算を連結するときに真価を発揮するので、例を使ってもっと見ていきましょう。例を分解すると、以下のように考えることが出来ます。

1. 次のターンで派生するボードをリストとして生成する
2. 以下の処理を繰り返す：派生するボードをCとすると、CをCのあとに派生するボードで置き換える
3. これでリストのリスト（リストの中のリストはそれぞれ前のターンからの派生を表しています）が生成されるので、これらの処理を繰り返すためにリストのリストからただのリストにまで崩す

この構造は上記のモナドインスタンス定義のそれと似て見えるはずです。リストモナドを利用しなかった場合、以下のように書けるかと思います。

getNextConfigs :: Board -> [Board]
getNextConfigs = undefined -- どうでもいいので書きません

tick :: [Board] -> [Board]
tick bds = concatMap getNextConfigs bds

find3rdConfig :: Board -> [Board]
find3rdConfig bd = tick $ tick $ tick [bd]

concatMapはmapの結果を結合しなくてはならない時に役に立ちます。

concatMap f x = concat (map f xs)

これをリストモナドで書くと、以下のように書くことが出来ます。

find3rdConfig :: Board -> [Board]
find3rdConfig bd0 = do
	bd1 <- getNextConfigs bd0
	bd2 <- getNextConfigs bd1
	bd3 <- getNextConfigs bd2
	return bd3