2008-12-24
■ memo 
圏論でのモナドを構成する三人組と、それに対するApplicative,Functorでの対応
| 関手(map) | 単位(unit) | 乗法(flatten) | |
|---|---|---|---|
| 型 | (a -> b) -> (m a -> m b) | a -> ma | m (m a) -> m a |
| Functor | fmap | ||
| Applicative | <$> | pure | |
| Monad | liftM | return | join |
Functor Laws
fmap id == id fmap (f . g) == fmap f . fmap g
Applicative Laws
--identity pure id <*> v = v --composition pure (.) <*> u <*> v <*> w = u <*> (v <*> w) --homomorphism pure f <*> pure x = pure (f x) --interchange u <*> pure y = pure ($ y) <*> u
Monad Laws
return a >>= k == k a m >>= return == m m >>= (\x -> k x >>= h) == (m >>= k) >>= h
Haskell generally uses a pair of functions called return and bind (>>=), but it is more natural sometimes to begin with map (fmap), return and join
(訳:Haskellは一般にreturnやbindと呼ばれる関数のペアを使うが、map(fmap),return,joinからはじめたほうがより自然である。)
Monads as containers - HaskellWiki
Monad は操作の積の抽象化ともいえる． 任意の a, b について、自然な (>>=) :: m a -> (a -> m b) -> m b が与えられるということは、任意の a について自然な m m a -> m a が与えられることと同値になる．これが積の正体． 2重配列を1重に直す Array#flatten は、この手の積の一例．
Haskell
■ モナドの勘所
http://d.hatena.ne.jp/m-hiyama/20060421/1145613700
http://d.hatena.ne.jp/m-hiyama/20060418/1145322223
ここを見ながらお勉強。少しだけモナドに親しくなれた気がする。
概要
いきなり脱線:無視しましょう。
普通、圏論で使われるのは、Haskellで言うところの(=<<)であるが、Haskellは(>>=)の方を優遇している。これはflip(=<<)なので意味的には同じで引数の順番が違う。(>>=)が優遇されているのは、流れを左から右にしたいからであろう。そうすれば、シンタックスシュガーであるdo記法に書き換えたときに、処理を上から下に書ける命令的スタイルと相性がいいのである。
普通の関数適用で考えてみよう。f (g (a))という関数があったとき、流れは右から左になっている。
次の関数で考える。
hoge = blur $ fizz $ buzz $ bar $ a
このときaにbarが適用され,それにbuzzが適用され,それにfizzが適用され,blurが適用され、という風に流れが下から上になっている。($$)をflip($)で定義し、結合性や優先順位を適切に設定すれば、
hoge = a $$ bar $$ buzz $$ fizz $$ blur
と書ける。こうすれば流れは上から下になってくれる。そういう事がしたいのでHaskellでは(=<<)より(>>=)を選んだと思われる。
さて、そういうHaskellの都合は無視しよう。
今ここにHaskellにおける関数(=<<),returnが存在するとする。
これらは圏論の用語ではそれぞれextとunitと呼ばれる。この二つと型構成子mを合わせてKleisli tripleと呼び、モナドの定義に使われる。
具体的には、次のモナド則を満たさなければならない。
1. (return x) >>= f == f x 2. m >>= return == m 3. (m >>= f) >>= g == m >>= (\x -> f x >>= g)
圏論のモナドの定義には代数スタイルという別の手段があり、それは(unit,fmap,join,型構成子)を元に作られる。(下の方で、Kleisli tripleからfmap,joinを作れる事を議論する。)
モナドと関係の無い普通の関数「f::A -> B」を仮定する。
この関数に「unit::a -> m a」を後合成することで「unit.f::A-> m B」の形の関数を得られる。
型が「(ほにゃらら)-> m (なんたら)」な関数をM resulticな関数と言う。要するにモナドを返す関数である。
普通の関数はunitと後合成することでM resulticな関数に出来る
- 圏論の議論より、M resulticな関数「(ほにゃらら)->m a」はext(=<<)を適用することで、お尻を持ちあげられる。つまり「m(ほにゃらら)→ m a」となる。
与えられたm a型の値をそのまま返す関数id::m a -> m a は「(ほにゃらら)-> m a」の形になっているのでM resulticである。M resulticな関数のお尻は持ちあげられるのでやってみると「id^:m(m a) -> m a」という形になる。
こいつがjoinの正体であり、Listのconcatの正体でもある。この関数を使えば多重なmを一段減らせる。
mが多段になっていたとしても(Maybe Maybe Maybe Maybe Maybe Maybe Int)、何度も適用すれば最後には1段まで落とせる(Maybe Int)
extからjoinが作れる。そしてjoinを使えばどんなモナドも1段まで落とせる。
- 圏論の議論より、M resulticで無い関数「(ほにゃらら)→a」にextは適用できない(お尻だけ持ちあげることはできない。)
ということは、extを使って「(ほにゃらら)->X」から「m(ほにゃらら)->X」を作ることができないという事を意味する。(unitを使っても無理である。)今作るのに断念した「m(ほにゃらら)->X」は、モナドを外す関数である。つまりモナドの外側をはいで1段のモナドまで落とすことはできても、最後のmを脱がせるようなモナド的な操作は存在しない。 「モナドには出口が無い」というのは、そういう意味である。
2つのM resulticな関数を合成し、1つのM resulticな関数を作れる.f:X→m Y とg:Y→m Zという関数があったとする。まずgのお尻を持ちあげてg^:m Y-> m Zという関数を作る。fの値域とg^の定義域は同じm Yなので、この二つは合成できる。その結果、g^.f:X->m Z が出きる。この2つのM-resulticな関数の合成をKleisli Compsitionと呼ぶ。
Control.Monadではモナド合成演算(Kleisli composition演算子)は次のように定義されている。
(>=>) :: Monad m => (a -> m b) -> (b -> m c) -> a -> m c m >=> n = \x -> do { y <- m x; n y }(訳注：これを変形する。
m >=> n = \x -> m x >>= \y->n y -- シンタックスシュガー外し m >=> n = \x -> m x >>= n -- ポイントフリー m >=> n = \x -> n =<< m x -- (=<<)はflip(>>=) m >=> n = \x -> (=<<) n (m x) -- 演算子は関数 m >=> n = \x -> (ext n) (m x) -- 議論にあわせてextに書き換え。nを部分適用 m >=> n = \x -> (ext n.m) x -- 関数合成 m >=> n = ext n.m -- ポイントフリー上で議論した形になった。
ところで、
a >>= b >>= c >>= d >>= e >>= f
は
a >>= (b >=> c >=> d >=> e >=> f)
と意味的に一緒である。>>=がやってるのは「b,c,d,e,fを合成した関数」のお尻を持ちあげて(拡張)aという座薬を入れる(適用)しているイメージである。
)
この演算子を使えば、Monad則は次のように書き換えられる。
- "Left identity": return >=> g = g
- "Right identity": f >=> return = f
- "Associativity": (f >=> g) >=> h = f >=> (g >=> h)
いまや、モナド合成が結合律を満たすのは明らかだ
Monad laws - HaskellWiki
手動の型推論により、return:a -> m a、f:a -> m b、g:b -> m a、h:a -> m c のはずなので
- a-> m a >=> a -> m b = a -> m b
- b -> m a >=> a -> m a = b -> m a
- (a -> m b >==> b -> m a ) >=> a -> m c = a->m b >=> ( b -> m a >=> a-> m c )
と書き換えることが出来る。
return を one,>=>を *** と書き換えると
one *** g = g f *** one = f (f *** g) *** h = f *** (g *** h)
掛算のように見えてくる。これを M-resulticな関数は、Kleisli compositionについて、unitを単位元とするモノイドになっていると表現する。(訂正：型が合致しなければならない制約があるために、正確にはモノイドでは無いそうです)
ところで、
- X->YからX->m Y
- -あるM-resulticでない関数にunitを後合成すると、頭を持ち上げたM resulticな関数が作れる
- X->m Yからm X->m Y
- M resulticな関数にextを適用すると、お尻を持ちあげた関数が作れる
この二つの操作を組み合わせればX->Yの全身を持ちあげたm X->m Yが作れる。こいつをmapと呼ぶ。これはHaskellではFunctorクラスのfmapであり(ちなみに、Haskellのリスト関数であるmapをfmapに全て置換しても、そのまま動く。)、MonadクラスのliftMである。
ここでついにjoinに続いてfmapを作ることができた。つまり(unit,fmap,join,型構成子)が揃ったことになる。つまりKleisli tripleで代数スタイルは表現できるということだ。
- (a-> ____ b) (___にはmが0個以上並んでいるとする)という関数は、なんでも a-> m bという形に出来る
- a-> b を a-> m bに出来る。(unitを後合成)
- a-> m......m b (たくさんmが並んでいると考えて。)を a ->m bに出来る。(joinとextを使う)
- ( )-> m ( )という形の関数同士をKleisli Compositionで合成し、型が( )-> m ( )の形になるようなひとつの関数にできる
結合律とモジュール性
上で、「モナドを返す関数はKleisli Compositionについてモノイド」になっているという事、かけ算にそこが似ている事を述べた。逆に言えば、かけ算について考えることはモナドについて考えることにもなる。
かけ算は結合律をみたす
A * C * C * D * C * C * F * C * C
これは
A * (C * C) * D * (C * C) * F * (C * C)
と同じである。こう書けるのは結合律のおかげである。
割り算は結合律が働かない。
120 / 2/ 3 / 4 = 5 120 /( 2/ 3)/ 4 = 45
C*Cを3回計算しているので、ここを「モジュール」としてくくりだそう。
C2 = C*Cとする。そうすれば次のように書ける。
A * C2 * D * C2 * F * C2
これが結合律の力である。
さらにモジュールに出来る。
C2 = C*C (A * C2) * (D * C2) * (F * C2)
f(n) = n * C2 と定義する。
C2=C*C f(n) = n * C2 f(A)* f(D) * f(F)
これと全く同じ事がモナドにも言える。
モナド則の結合律のおかげで、モナドを返す関数(M-resultic)の組み合わせ(Kleisli Composition)は、その一部を取り出して自由にモジュールにできる。そして、(まだ僕には)なぜかは良くわからないが、いろんな処理がモナドで表現できるのである。それはつまり、いろんな処理を自由にモジュールに分割できる、という事である。
main = do uguu
gao
poka
anpan
gao
poka
は次と同じで
air = do gao poka main = do uguu air anpan air
これは次と同じである。
crossworld kuchiguse = do kuchiguse air air = do gao poka main = do crossworld uguu crossworld anpan
こんな事が出来るのは結合律のおかげである。
かけ算についての上のモジュール性の議論を、実際にHaskellを使って真似てみよう。
a = 5 d = 10 f = 8 c = 3 ret :: Int->Int ret n = n (>>>=):: Int->(Int->Int)->Int a >>>= f = f a multiply :: Int->(Int -> Int) multiply a b = (a*b) data MyInt = MyInt Int deriving (Show,Eq) --A * C * C * D * C * C * F * C * C ans = ret 1 >>>= multiply a >>>= multiply c >>>= multiply c >>>= multiply d >>>= multiply c >>>= multiply c >>>= multiply f >>>= multiply c >>>= multiply c -- A * C2 * D * C2 * F * C2 c2 = \n-> ret n >>>= multiply c>>>= multiply c ans2= ret 1 >>>= multiply a >>>= c2 >>>= multiply d >>>= c2 >>>= multiply f >>>= c2 --f(A)* f(D) * f(F) fun x = \n-> ret n >>>= multiply x >>>= c2 ans3= ret 1 >>>= fun a >>>= fun d >>>= fun f
実行結果
*Main> ans 291600 *Main> ans2 291600 *Main> ans3 291600
恒等モナドを使って書き直す。
import Control.Monad.Identity a = 5 d = 10 f = 8 c = 3 multiply :: Int-> (Int -> Identity Int) multiply a b = return (a*b) --A * C * C * D * C * C * F * C * C ans = return 1 >>= multiply a >>= multiply c >>= multiply c >>= multiply d >>= multiply c >>= multiply c >>= multiply f >>= multiply c >>= multiply c c2 = multiply c >=> multiply c -- A * C2 * D * C2 * F * C2 ans2= return 1 >>= multiply a >>= c2 >>= multiply d >>= c2 >>= multiply f >>= c2 fun x = multiply x >=> c2 --f(A)* f(D) * f(F) ans3= return 1 >>= fun a >>= fun d >>= fun f
