リストモナド

関数型イカ娘の影響で再びHaskell熱が盛り返して参りました。

前回Haskellを勉強したときに理解できなかったモナドをとりあえず理解したいと思って勉強中です。
理解したこととかを備忘録的にメモっておく。
今回はリストモナド。続くかは未定。

モナドの核はおそらくこれ。

(>>=) :: m a -> (a -> m b) -> m b
(>>) :: m a -> m b -> m b
return :: a -> m a

モナド則なるものもあるのだが、とりあえず使う立場からはそんなに気にしなくてよさそう。
ただし

a >> b

は

a >>= (\_ -> b)

のシンタックスシュガーなのはちょっと重要。

この定義がなんのモナドなのかによって決まる。

リストモナドの場合はこれらが

m >>= k          = concat (map k m)
return x         = [x]

になる。

リストモナドを使うとこういうことができるらしい(たぶん本質はまた別にあるのだろうが、とりあえず動作が理解できなかったのでこの例を挙げる)。

do{ x <- [1,2]; y <- [3,4]; return [x, y]; }          -- [[1,3],[1,4],[2,3],[2,4]]
do{ x <- [1..100]; guard(x > 3 && x < 10); return x } -- [4,5,6,7,8,9]

たぶんモナド初心者はパッと見では理解出来ないのではないか。というか私がパッとは理解できなかったものを挙げている。
一見、xやyはリストのはずなのに、あたかもその要素であるかのように扱っている(ように私には)見える。
ではこれは一体どうなっているのか。

モナド系はdo記法を使うと書きやすく(そしてたぶん分かる人にはわかりやすく)なるが、初心者が意味を理解する場合には定義に戻っていったほうが良いと思う。

doの中でのa <- b; hogeは b >>= (\a -> hoge)、foo; barはfoo >> bar、つまりfoo >>= (\_ -> bar)になる。これを使って先ほどの最初の例を変形していくと、

do{ x <- [1,2]; y <- [3,4]; return [x, y]; }
-- do を展開
[1,2] >>= (\x -> [3,4] >>= (\y -> return [x,y]))
-- >>= を展開
concat (map (\x -> [3,4] >>= (\y -> return [x,y])) [1,2])
-- もういっちょ
concat (map (\x -> concat (map (\y -> return [x, y]) [3,4])) [1,2])

ここまで来ると、上で書いた要素ごとに扱っているように見えるというのが理解できる。
というかリストモナドとはそういう風に作っているのだろう、、、たぶん。
ここが個人的に最初の壁だった。

次は下の例、こちらで疑問に思ったのは、xは[1..100]であるはずなのに、guard()をはさむと値が変わっているように見えることである。
とりあえず変形しよう。

do{ x <- [1..100]; guard(x > 3 && x < 10); return x }
-- do を展開
[1..100] >>= (\x -> guard(x > 3 && x < 10) >> return x)
-- >> を展開
[1..100] >>= (\x -> guard(x > 3 && x < 10) >>= (\_ ->  return x))
-- >>= を展開
concat (map (\x -> guard(x > 3 && x < 10) >>= (\_ ->  return x)) [1..100])
-- もういっちょ
concat (map (\x -> concat (map (\_ -> return x) (guard(x > 3 && x < 10)))) [1..100])

guardは

guard p          =  if p then return () else mzero
-- リストの場合は、 if p then [()] else [] だと思えばいい

となっている。つまり、条件が満たされていれば、[()]が返ってきて、(\_ -> return x)により、xが残るのでたしかにそういう結果になりそうだ。

うーん、確かにそうなるのはわかったけど、なんかしっくりこない感じ。
いつかこれがしっくりくる日がくるのだろうか・・・。

参考
http://blog.netswitch.jp/2008/02/19/haskell-do-notation
http://itpro.nikkeibp.co.jp/article/COLUMN/20061031/252259/
http://d.hatena.ne.jp/kazu-yamamoto/20090401/1238555013