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

めもめも

このブログに記載の内容は個人の見解であり、必ずしも所属組織の立場、戦略、意見を代表するものではありません。

Monadのbind結合則に関する小ネタ

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, ...]に変換されることが分かります。すっきり。