filterM を使って、べき集合を表すことができる。
*Main Control.Monad> filterM (\x -> [True, False]) [1..3]
[[1,2,3],[1,2],[1,3],[1],[2,3],[2],[3],[]]
filterM は、述語にモナド値を返す関数を取ることができるので、この場合は非決定性計算 の文脈を付けられることになる。つまり、[1..3] のそれぞれの要素に対して、対象とするパターンと対象外とするパターンを試し、答えになり得るリストを全て出力することができる。これは、べき集合（与えられた集合から、その部分集合の全体として新たに作り出される集合）である。
と、日本語で書いてみると確かにそうなりそうだなぁと思えるのだが、定義を見てみたら頭がこんがらがってしまったので整理することにした。
実際のところ、非決定性計算 ＋ 畳み込み関数 という、内部の操作が膨れ上がりそうな定義を見て胸がウッとなったのが、今回の動機である。
filterM の定義を覗く
filterM :: (Monad m) => (a -> m Bool) -> [a] -> m [a]
filterM p = foldr go (return [])
where
go x r = do
flg <- p x
ys <- r
return (if flg then x:ys else ys)
とりあえず、 filterM 関数の実体は foldr 関数であり、その引数に go というモナド値を返す関数を取っていることがわかる。畳み込み操作にこのような関数を使うとどうなるのか。これは、文脈を維持して値を畳み込んでいくということなので、今回はリストのリストがどんどん出来上がっていくことになる。
go 関数を >>= で表す
定義に沿って、内容を確かめるために、上記の go 関数を書き換える。局所関数なのでこのコードは正しくないが、雰囲気としてはこのようになる。
go x r = p x >>= (\flg ->
r >>= (\ys ->
return (if flg then x:ys else ys)))
リストモナドの定義は次のようになっている。
instance Monad [] where
xs >>= f = [y | x <- xs, y <- f x]
つまり、リストモナドの場合、 >>= は左辺のリストの各要素に右辺の関数を適用した結果（この結果はリストになる）を連結している。
この操作を go 関数に当てはめてみると、x を引数に取って作られた p x ( Bool のリスト )の各要素を r ( リストのリスト )に置き換えて、この時Bool のリストの要素が True なら対応するリストのリストの要素の先頭に x をくっつけるがFalse なら何もしない、ということになる。なるほどわかりにくい。
図解してみる
ここで、 filterM (\x -> [True, False]) [1..3] をfoldr で表してみると、
filterM (\x -> [True, False]) [1..3]
1 => foldr go (return []) [1..3]
2 => go 1 (go 2 (go 3 (return [])))
3 => go 1 (go 2 ([ y | x <- [True, False], y <- (\z -> return []) x ] ])
4 => go 1 (go 2 ( [[], []]))
5 => go 1 (go 2 ( [[3], []]))
6 => go 1 [ y | x <- [True, False], y <- (\z -> return [[3], []]) ]
7 => go 1 [ [3], [], [3], []] ]
8 => go 1 [ [2,3], [2], [3], [] ]
9 => [ y | x <- [True, False], y <- (\z -> return [ [2,3], [2], [3], [] ])]
10 => [[2,3], [2], [3], [], [2,3], [2], [3], []]
11 => [[1,2,3], [1,2], [1,3], [1], [2,3], [2], [3], []]
上の５行目から８行目までを図解してみると、少し理解が進みそう。
go 関数の第一引数がBool のリストになり、True と False のそれぞれがアキュムレータで置き換わるために、再帰されるたびに全体の要素数が２倍になっているということがわかる。
終わりに
一旦は何をやっているのか腑に落ちたものの、また忘れそうな気がする。このページは私自身何度も見ることになりそう。