MonadFixの理解のために(2)---リストモナドでmfix考える1
かなりfixを使ってみたので，そもそもの本題に向かいます．
リストはMonad
ひとまず，リストはモナドであることの定義は
instance Monad [] where m >>= k = foldr ((++) . k) [] m m >> k = foldr ((++) . (\ _ -> k)) [] m return x = [x] fail _ = []
となってます．これがモナド則
return a >>= k == k a -- (1) m >>= return == m -- (2) m >>= (\x -> k x >>= h) == (m >>= k) >>= h -- (3)
を満たすことを追いかけてみます（(>>=)はconcatMapそのものですが，あえてGHC.baseの記述にしたがってfoldrのまま進んでみます）．
-- (1) return x >>= k == [x] >>= k == foldr ((++).k) [] [x] == foldr g [] [x] -- g = (++).k :: a->[b]->[b] == g x [] == k a++[] == k a -- (2) m >>= return == foldr ((++) . return) [] m == foldr g [] [a1,a2,...,an] -- m = [a1,a2,...,an], g = (++).return::a->[b]->[b] == g a1 (g a2 g (... g an []...)) == g a1 (a a2 g (...g an-1 [an]...)) == [a1,a2,...,an] == m -- (3) m >>= (\x -> k x >>= h) == m >>= f -- f x = k x >>= h == foldr ((++).f) [] [a1,a2,...,an] -- m = [a1,a2,...,an] == foldr g [] [a1,a2,...,an] -- g = (++).f ::a->[b]->[b] == g a1 (g a2 g (... g an []...)) == f a1 ++ f a2 ++ ... + f an ここで f ai == k ai >> h == foldr ((++).h) [] k ai == h b1 ++ h b2 ++ ... ++ h bm -- k ai = [b1,...bm] == k a1の各要素をhで変換して，それを連結したリスト であり，k aiはaiをk変換して得られるリストであることを考えれば f a1 ++ f a2 ++ ... + f an == [ai,...,an]=mの各要素をkで変換してそれを連結してできるリストに対して 各要素をhで変換して，それを連結してできたリスト 一方， (m>>=k)>>=h == foldr ((++).h) [] (m>>k) == foldr ((++).h) [] (foldr ((++).k) [] m) == foldr ((++).h) [] (k a1 ++(k a2++(...++ (k an-1)++(k an)))) == foldr ((++).h) [] (k a1 ++ k a2 ++ ... + k an) == h c1 ++ h c2 ++ ... + h cm' -- k a1 ++ k a2 ++ ... + k an=[c1,c2,...,cm'] == m の各要素を先頭からkで変換して，それを連結したリストに対して， 各要素をhで変換して，それを連結してできたリスト したがって， m >>= (\x -> k x >>= h) == (m >>= k) >>= h
(3)だけは記号で進めると混乱しますが，意味的に考えるとかなり楽です．(>>=)は結局のところ，左側にあるリスト（モナド）の各要素を右の関数で変換してそれを連結します．例えば，[1,2,3]>>=(\x->[2*x])は[1,2,3]のそれぞれの要素に対して，[2]，[4]，[6]というリストを作ってそれを連結することで，[2,4,6]を作ります（concatMap (\x->[2*x]) [1,2,3]です）．
こう考えれば，m>>=k>>=hはmの要素をkで変換して連結して，その要素を更にhで変換して連結したものです．一方のm >>= (\x -> k x >>= h)の右辺の関数は，要素xをリストkxにして，その各要素をhで変換して連結する関数ですが，左の(>>=)によってxにはmの各要素が入ってきますので，結局mの要素をkで変換して連結したリストの各要素をhで変換して連結したリストです．順番が入れ替わらないことにも注意です．
言葉で書くとややこしいですが（式で書くと記号が氾濫して大変），実際に簡単なサンプルを作ればすぐ分かります．例えば
f x = [2*x] g c = [x*x] [1,2,3]>>=f>>=g == [2,4,6]>>=g == [4,16,36] [1,2,3]>>=(\x->f x>>=g) == [f 1 >>= g]++[f 2 >>= g]++[f 3 >>= g] == ([2]>>=g)++([4]>>=g)++([6]>>=g) == [4]++[16]++[36] == [4,16,36]
です．
リスト内包表記はdo記法
さて，リスト内包表記で
[ (x,y) | x<-[1,2,3], y<-[2,4,6], 2*x==y ]
という，[(1,2),(2,4),(3,6)]となるのは明らかものを考えてみます．リスト内包表記はモナドであるリストのdo記法の糖衣構文だなんてよくでているわけで，
-- A Gentlec Introduction to Haskel Version 98 の形式 do x<-[1,2,3] y<-[2,4,6] True <- return (2*x==y) -- returnでは[Bool]が返され，Trueの要素のみがとりだされることになる． return (x,y)
と等価だと書かれています．そもそもこれが冷静になるとちょっと不安です．すぐわかるのは，リスト内包表記では順番が大事だということです．2*x==yを最後，すくなくともxとyよりも後に書かないと``Not in scope''といわれるので，順番に処理されるというモナドの性質が垣間見れます．そして，do記法は
do {e1; e2} == e1 >> e2 do {p<-e1; e2} == e1 >>= (\p->e2) do {p<-e1; e2} == e1 >>= (\v -> case v of p -> e2 _ -> fail "s") -- s は何かの文字列
といわれてますが，実際にはどうなるのでしょうか．
-- 条件をとってみる do x<-m --m=[1,2,3] y<-n --n=[2,4,6] -- True <- return (2*x==y) return (x,y)
を>>=とreturnにしてみます．>>=は左結合なので
(m >>= f)) >>= return (x,y) -- とりあえず直訳．fはy<-[2,4,6]に相当 m >>= (\x -> (f x >>= return (x,y))) -- モナド則で変換．あえて括弧を多めに． m >>= (\x -> (n >>= (\y -> return (x,y) ) )) -- 同じ規則で変換
さて，条件を復活させてみます．
-- 再掲 do x<-m -- m=[1,2,3] y<-n -- n=[2,4,6] True <- return (2*x==y) return (x,y)
これを>>=とreturnになおすと，
( (m >>= f) >>= g) >>= return (x,y) -- とりあえず直訳． -- fはy<-[2,4,6]に，gは True <- return (2*x==y)に対応 (m >>= (\x -> f x >>= g)) >>= return (x,y) -- モナド則 (m >>= h) >>= return (x,y) -- h = \x -> f x >>= g m >>= (\x -> h x >>= return (x,y)) -- モナド則 m >>= (\x -> (f x >>= g) >>= return (x,y) ) m >>= (\x -> f x >>= (\y-> g y >>=return (x,y))) m >>= (\x -> n >>= (\y -> g y >>= return (x,y))) -- f xはnのこと m >>= (\x -> n >>= (\y -> return(2*x==y) -- g y >>= return はcaseに変換される >>= (\r -> case r of True -> return (x,y) _ -> fail "")))
難読です。。読めません。ただし，do記法でreturnで返ってくるものを何か固定した値に束縛すると，内部でcaseになるので，その束縛に適したものを取り出せるというのは面白いです．例えば，
do x<-[1,2,3] y<-[2,4,6] 2 <- return x return (x,y)
とすると[(2,2),(2,4),(2,6)]とx=2のものだけがでてきます．しかもリストモナドのfailは空リスト[]を返すものなので，整合がとれています．実に巧妙に設計されています．
モナドでは再帰的な束縛はできない．
例によってmdoの論文（A recursive do for Haskell, by Levent Erk\"ok, John Launchbury, Haskell Workshop 2002, pages: 29-37. Pittsburgh, Pennsylvania）から拝借します．
問題（pairwise swap）
二分木の各リーフの値から二つを選んで，それを取り替えた木をすべて列挙せよ．ただし，二つ選ぶときには「同じもの」を選んでもよいし，選ぶ順番は区別する．例えば，data Tree = L Int | N Tree Tree deriving Showとしたとき，(L 1)はTreeであり，「取り替えた結果の木」は(L 1)である．N (L 1) (L 2)に対しては，N (L 1) (L 2)，N (L 2) (L 1)，N (L 2) (L 1)，N (L 1) (L 2)が結果である．これはそれぞれ，1と1，1と2，2と1、2と2の交換に対応する．N (L 1) (L 1)に対しては，N (L 1) (L 1)が四個という結果となる．また， (N (N (L 1) (L 2)) (L 3))に対しては
N (N (L 1) (L 2)) (L 3), N (N (L 2) (L 1)) (L 3), N (N (L 3) (L 2)) (L 1), N (N (L 2) (L 1)) (L 3), N (N (L 1) (L 2)) (L 3), N (N (L 1) (L 3)) (L 2), N (N (L 3) (L 2)) (L 1), N (N (L 1) (L 3)) (L 2), N (N (L 1) (L 2)) (L 3)]の九つが結果となる．対角成分がそれぞれ1と1，2と2，3と3の交換に対応し，1と2，1と3、2と3の交換が上の三角成分に，これらの反対の交換が下の三角成分に対応する．
容易に分かるように，リーフがn個ならば，結果はn^2個存在する．
この問題はrepminとある意味で同じです．repminでは「最小値の候補」をリーフの値に収めていって，もともとの値は外に出して小さいものを残していくような操作でした．このpairwise swapでは，適当な値で中身を取り替えていって，それを全部リストに入れる操作がでてきます（repminでは全部ではなく最小値だけを取り出しました）．そうしてできたリストの各要素に対して，今度は逆に，「取り出された要素」とリーフの中身を交換していきます．そうしてできた木のリストがこの問題の答えになるはずです．
これをコードにするとこういう感じです．
data Tree = L Int | N Tree Tree deriving Show replace:: Int ->Tree replace x (L y) = [(L x,y)] replace x (N l r) = [(N l' r, y) | (l',y) <- replace x l ] ++ [(N l r', y) | (r',y) <- replace x r ] -- このpairSwapsは動きません！ pairSwaps :: Tree -> [Tree] pairSwaps e = do (e',m) <- replace n e (e'',n) <- replace m e' return e''
手を動かしてみます．まずpairSwaps (L 1)を考えます．答えは(L 1)です．
replace n (L 1) = [((L n), 1)]
を(e',m)に束縛するので，e'=(L 1)，m=1です．これに対して
replace m e' =replace 1 (L 1) = [(L 1),1]
となるので，e''=(L 1)，n=1です．したがって，return e''は[(L 1)]です．
N (L 1) (L 2)に対してはどうでしょうか．地道に考えます．
replace n (N (L 1) (L 2)) = [(N l' (L 2),y) | (l',y) <- replace n (L 1)] ++ [(N (L 1) r',y) | (r',y) <- replace n (L 2) = [((N (L n) (L 2)),1) ((N (L 1) (L n)),2)]
となります．リーフの値と「適当な値n」を交換して，もともとの値が外にでたリストができました．これをdo記法の次の行におくる，つまり>>=で処理するのはconcatMapそのものでした．したがって，
[replace 1 (N (L n) (L 2))] ++ [replace 2 (N (L 1) (L n))] = [((N (L 1) (L 2)),n), ((N (L n) (L 1)),2)] ++ [((N (L 2) (L n)),1), ((N (L 1) (L 2)),n)]
が現れます．この四つの要素をそれぞれ(e'',n)に束縛するので，
e''=(N (L 1) (L 2)) n=n e''=(N (L n) (L 1)) n=2 e''=(N (L 2) (L n)) n=1 e''=(N (L 1) (L 2)) n=n
という四つの要素がでてきて，最初と最後のものはnが評価されることなく，残りの二つはnがそれぞれ2と1に評価されて，それぞれがreturnに送られて，リストとして結合されて
[N (L 1) (L 2), N (L 2) (L 1), N (L 2) (L 1), N (L 1) (L 2)]
が得られます．
- do記法の最初の(e',m) <- replace n eでまず，eのリーフの値を一個ずつnにおきかえて，それぞれの置換後の木をe'に，追い出された値をmに束縛する．
- 次の(e',n) <- replace m e'で，置換後のe'のリーフの値を一個ずつ，最初に追い出されたmの値で置換して，置換後のものをe''に，今度の置換で追い出された値をnに束縛する．
- 二回目に追い出された値が最初の置換のnなら，e''にはnはなく，nは評価されず，e''がそのまま解のリストの要素になる．
- 二回目に追い出された値が最初の置換のnではない（確定した値）なら，e''には値がnのリーフがあるが，nは追い出された値に評価され，その結果e''が解のリストの要素になる．
- もともとのリーフの個数をkとすると，最初の置換で要素数kのリーフ数kの木のリストができ，さらにそれぞれの要素に対して要素数kのリストができ，連結されるので要素数k^2のリストができる
という流れです．
しかし・・・大きな問題があります．
pairSwaps e = do (e',m) <- replace n e (e'',n) <- replace m e' return e''
を>>=にすると
pairSwaps e = replace n e >>= (\(e',m) -> replace m e') >>= (\(e'',n) -> return e'')
となりますが，モナドには順番があります．そもそも最初のnはどこからくるのでしょう？そして，そのnは最後のnと同じでしょうか？ということで，do記法ではこういう再帰的な束縛はできません．
困りました．再帰的な束縛さえできれば問題ないのは分かっているのに何か手がないのでしょうか．
