他人のHaskell日記 RSSフィード

Haskell初心者が、リハビリがてらに「ふつける」と「入門Haskell」片手に、試行錯誤するサイト。

2008-12-24

memo memo - 他人のHaskell日記 を含むブックマーク

圏論でのモナドを構成する三人組と、それに対する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からはじめたほうがより自然である。)

no title

Monad は操作の積の抽象化ともいえる. 任意の a, b について、自然な (>>=) :: m a -> (a -> m b) -> m b が与えられるということは、任意の a について自然な m m a -> m a が与えられることと同値になる.これが積の正体. 2重配列を1重に直す Array#flatten は、この手の積の一例.

no title


モナドの勘所 モナドの勘所 - 他人のHaskell日記 を含むブックマーク

http://d.hatena.ne.jp/m-hiyama/20060421/1145613700

http://d.hatena.ne.jp/m-hiyama/20060418/1145322223

ここを見ながらお勉強。少しだけモナドに親しくなれた気がする。

概要

  • どんな関数も「(1段の)モナド」を返す関数に変換できるよ。
  • モナドを返す関数」同士を合成して「モナドを返す関数」にできるよ。
  • その合成には結合律が成り立つよ。
  • 結合律はモジュール性を産むよ。

いきなり脱線:無視しましょう。

普通、圏論で使われるのは、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)

いまや、モナド合成が結合律を満たすのは明らかだ

no title

手動の型推論により、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       

BiancaBianca2012/07/24 08:45Deadly accuarte answer. You've hit the bullseye!

iokinaqiokinaq2012/07/25 02:21eAffTE <a href="http://wnespfgrntru.com/">wnespfgrntru</a>

rzefrqgrzefrqg2012/07/26 00:16awec8R , [url=http://waphzksgulwp.com/]waphzksgulwp[/url], [link=http://xqmarjiugccf.com/]xqmarjiugccf[/link], http://aszaetsvysvt.com/

bcwwspbcwwsp2012/07/26 19:06UvNa0Y <a href="http://iicmmzekucpv.com/">iicmmzekucpv</a>

バイアグラバイアグラ2012/11/29 16:04バイアグラジェネリックのhttp://xn--ed-u41gn1j.net/
バイアグラジェネリックの販売 購入はed通販で。
ED治療薬のバイアグラジェネリックの個人輸入を完全サポート致します。
http://xn--ed-u41gn1j.net/generic100.html
バイアグラジェネリック バイアグラジェネリック通販 バイアグラジェネリック販売