bindの結合則
Monadのbind演算(>>=)の結合則は次の様に表現されます。
(m >>= f) >>= g ≡ m >>= (\x -> f x >>= g)
なんで素直にこう書かないの？
(m >>= f) >>= g ≡ m >>= (f >>= g) ← 間違い
と思ったあなたは、m,f,gの型を考えましょう。
m :: m a f :: a -> m b g :: b -> m c
一方、bind演算の型はこう。
>>= :: m a -> ( a -> m b ) -> m b
したがって、f >>= gという演算は、こんな意味になるので、>>=の型に合わずNGです。
f >>= g :: (a -> m b) >>= (b -> m c) ← 間違い
一方、ある特定の x :: a に対してf xの型はmbなので、次の演算はOKです。
for some x :: a; f x >>= g :: m b -> m c
ただし、実際にはxは特定できないので、Lamda抽象でこのように表現しておきます。
\x -> (f x >>= g) :: a -> m c
ここでまでくればお分かりですね。この式の型を見ると、これは"m >>="の右辺にくる事ができます。すっきり。
m >>= \x -> ( f x >>= g )
最初に示した結合則の右側をこのように解釈して、意味不明になっている方が意外と多いのではないでしょうか？
m >>= ( (\x -> f x) >> = g ) ← 間違い
foldlとfoldrの微妙な違い
ちょっと脱線ですが、foldl/foldrの復習。
お約束でまずは、定義だけ書いてみるとこんな感じですが、
foldr f z [] = z foldr f z (x:xs) = f x (foldr f z xs) foldl f z [] = z foldl f z (x:xs) = foldl f (f z x) xs
ざっくり言うと、foldlはリスト[a,b,c...,z]の要素を前から順番に取り出して、関数fに放り込みながら、ある初期値eを順番に変化させていく操作。例えば、初期値0に対して、fはリストの要素を足し算する関数だとすると、次の様に計算が進みます。
f 0 a = 0 + a = a
--------------|
|
v
f a b = a+b
-----|
|
v
f (a+b) c = a+b+cこの様に、fは前回の結果と新しい要素を受け取って、その結果をさらに次の演算に回します。
もう一方のfoldrは、リスト[a,b,c...,z]の要素を後ろから順番に取り出して演算していくものです。例えば、初期値0に対して、fはリストの要素を足し算する関数だとすると、次のように計算が進みます。
f z 0 = 0 + z = z
------------|
|
v
f y z = y+z
---|
|
v
f x (y+z) = x+y+zここで、foldlとfoldrでfの引数の順序が違うことに気づいたでしょうか。foldlに使うfは、"f 前回の結果 次の要素"なのに対して、foldrに使うfは"f 次の要素 前回の結果"になっています。リストの型を[x]、初期値eから変化していく一連の値の型をaとして、フォーマルに書くとこんな感じ。
foldl の f :: a -> x -> a foldr の f :: x -> a -> a
なぜこんな違いがあるのかは不明ですが、最初の定義がそうなっているから仕方ありません。
もしかしたら、こんなイメージ？
foldl
"a, b"までの結果 c <-------- d,e,...,z]
f
foldr
[a,b,...,w -----------> x "y, z"までの結果
f
応用編
bindの結合則とfoldl/foldrを思い出したら、ここで応用編です。sequence演算の定義を読み解きましょう。
sequence :: Monad m => [m a] -> m [a]
sequence = foldr mcons (return [])
where mcons p q = p >>= \x -> q >>= \y -> return (x:y)sequenceは、モナドのリスト[m a]をリストのモナドm[a]に変換する演算ですが、定義を見ると補助関数mconsでbind演算の結合則風なものが見えています。最初の教訓を活かして、正しく()付けしてみましょう。また、mconsはfoldrに適用する関数fなので、引数は、"mcons 次の要素 前回の結果"という事に注意して、"p=>n:次の要素、q=>result:前回の結果"という文字の置き換えも行います。
mcons p q = p >>= \x -> q >>= \y -> return (x:y) ↓ mcons p q = p >>= \x -> ( q >>= (\y -> return (x:y)) ) ↓ mcons n result = n >>= \x -> ( result >>= (\y -> return (x:y)) )
これを見ると、最初に与えられたnは、変数xを通って、最後のreturn (x:y)にそのまま入ります。同じく、resultは変数yを通って、最後のreturn (x:y)にそのまま入ります。Monad演算なので正確には、(MonadのコンストラクタをmkMとして）n=mkM a、result = mkM[b,c,d..]として、
return (x:y) = return (a:[b,c,d..]) = mkM[a,b,c,d,...]
この操作がfoldrによって、[mkM a, mkM b, mkM c...]の各要素について後ろから順番に行われることで、mkM[a, b, c, ...]に変換されることが分かります。すっきり。
