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

みどりねこ日記

よくわからないけど、頑張りますよ。

Haskellのモナド3(4)

Haskell

mplusとmzeroの他にも、いくつか知っておくべき関数があります。

msum
MonadPlusのインスタンスを扱っている時に、モナドのリスト[Maybe a]、つまり[[a]]を受け取ってそれをmplusで折りたたんでいくという作業をよく行います。msumがまさにそれです。

msum :: MonadPlus m => [m a] -> m a
msum = foldr mplus mzero

これは、リストの結合の一般化と考えれば良いです。実際、リストモナドに対するmsumはまさにリストの結合となります。Maybeモナドでは、リスト中の最初のJust xを見つけ、もしJust xが含まれていない場合、Nothingを返します。

guard
guardは、非常に便利な関数で、おそらく知らず知らずのうちに使ったことがあるかと思います。これはリスト内包表記の中でも用いられます。リスト内包表記をリストモナドに戻して書くと、以下のようになりますね。

pythags = [(x, y, z) | z <- [1..], x <- [1..z], y <- [x..z], x^2 + y^2 == z^2]

これは以下のように書きなおすことが出来ました。

pythags = do
	z <- [1..]
	x <- [1..z]
	y <- [x..z]
	guard (x^2 + y^2 == z^2)
	return (x, y, z)

guardの定義は以下のようになっています。

guard :: MonadPlus m => Bool -> m ()
guard True = return ()
guard False = mzero

具体的には、guardは引数がFalseであるなら呼んだdoブロックにmzeroを返します。MonadPlusの法則として、

mzero >>= hoge  == mzero

というのがありましたね。doブロックは>>=演算の塊ですので、mzeroが処理の中に入るとdoブロック全体がmzeroとなります。

もう少し説明するために、上のピタゴラス関数を拡張して、リストモナドの特別なguardを考えてみます。まず、以下がリストモナド用のguardです。

guard :: Bool -> [()]
guard True = [()]
guard False = []

guardは値を弾きます。例えば、ピタゴラス関数では、「x^2 + y^2 = z^2でない」すべての値を弾いてほしいです。先ほどのdo構文ピタゴラス関数を展開したものをみてみましょう。

pythags =
	[1..] >>= \z ->
	[1..z] >>= \x ->
	[x..z] >>= \y ->
	guard (x^2 + y^2 == z ^2) >>= \_ ->
	return (x, y, z)

(>>=)とreturnをリストモナドのそれに置き換えると、以下のようになります。

pythags =
	let ret x y z = [(x, y, z)]
		gd z x y = concatMap (\_ -> ret x y z) (guard $ x^2 + y^2 == z^2)
		doY z x = concatMap (gd z x) [x..z]
		doX z    = concatMap (doY z) [1..z]
		doZ       = concatMap (doX ) [1..]
	in doZ

もし与えられた引数がFlaseとなったとき、guardがカラリストを結果として返すことに気をつけてください。空リストに対してマッピングした場合、どのような関数を渡しても空リストにしかなりません。そのため、gdの中、guardによって作られた空リストはgdに結び付けられ、結果retは空リストとなります。

なぜこれが大切なのかは、リスト計算というものが木のようなものだと考えればわかります。ピタゴラスの三角形を探索するとき、まずzを決め、そこから派生する答えかもしれない可能性(木)の中、xを決め、そのxから派生する木からyを決める必要があります。ですので、このようなずになるかと思います。

start
	|__________________________________.....
z	1				2
	|				|
	|				...
	|
	|____....    ____________________.....
	|				|
x  1				1
	|
	|_________....
	|				|
y	1				1

x, y, zの組み合わせそれぞれが可能性を表しています。関数がこの木を評価し終わった時、木の下の方から結果をつなげていきます。結果が空リストであれば、この結合作業に全く影響しないので、結果演算が成功します。