Commits

blooper committed f72f6be

restore section about Cont

Comments (0)

Files changed (1)

join_to_Monad.rst

   join = (>>= id) = (id >=> id)
   f >=> g = \x -> (f x >>= g) = join . (liftM g) . f
 
+(>=>) と継続渡し
+----------------
+
+`モナドメモ - 具体的なモナド(Continuation) <http://www.sharp-bang.jp/prog/monad_memo_cont.html>`_ というページを見つけてしまいましたので、Monad と継続のことも少し考えなくちゃいけなくなりました::
+
+  $ hugs -98
+  __   __ __  __  ____   ___      _________________________________________
+  ||   || ||  || ||  || ||__      Hugs 98: Based on the Haskell 98 standard
+  ||___|| ||__|| ||__||  __||     Copyright (c) 1994-2005
+  ||---||         ___||           World Wide Web: http://haskell.org/hugs
+  ||   ||                         Bugs: http://hackage.haskell.org/trac/hugs
+  ||   || Version: September 2006 _________________________________________
+
+  Hugs mode: Restart with command line option +98 for Haskell 98 mode
+
+  Type :? for help
+  Hugs> :load Control.Monad.Cont
+  Control.Monad.Cont> :info Cont
+  -- type constructor
+  newtype Cont a b
+
+  -- constructors:
+  Cont :: ((b -> a) -> a) -> Cont a b
+  -- selectors:
+  runCont :: Cont a b -> (b -> a) -> a
+
+  -- instances:
+  instance Functor (Cont a)
+  instance Monad (Cont a)
+  instance MonadCont (Cont a)
+
+  Cont :: ((b -> a) -> a) -> Cont a b  -- data constructor
+
+Cont a b というのは、型 b の状態を保持しているらしく、継続するべき処理 b -> a を受けとるとその状態 b に適用しているのか結果として a を得るという、ややこしい型です。で、instance のところを見ると分かる通り、型 a を決める毎に Cont a という Monad が 1 つ定まります。Maybe とか List はそれだけで Monad でしたが、Cont は型を 1 つ決めると Monad が 1 つ決まって、更にもう 1 つの型を Monad の中身の型として取ります。
+
+Cont a の a は最終的に計算結果として得られる値の型を表現しています。状態 b から a を得る関数が Cont a b で、Cont という data constructor で関数であることが隠蔽されています。すごい簡単な使い方を見てみると::
+
+  Control.Monad.Cont> :type runCont (return 100)
+  runCont (return 100) :: Num a => (a -> b) -> b
+  Control.Monad.Cont> runCont (return 100) (+200)
+  300
+  Control.Monad.Cont> runCont (return 100) (*300)
+  30000
+
+と、どちらも 100 を与えられた関数に代入しています。代入と言い切ってしまっていいのは return の定義がそうだからで、ソースを見てると::
+
+  instance Monad (Cont r) where
+          return a = Cont ($ a)
+          m >>= k  = Cont $ \c -> runCont m $ \a -> runCont (k a) c
+
+となっています。($) は::
+
+  Control.Monad.Cont> :t ($)
+  ($) :: (a -> b) -> a -> b
+
+という関数適用そのものだったので、return は値だけ用意して作用させる関数を待っている形です。で、それを Cont という constructor に入れています。
+
+で、その下に (>>=) の定義がありますが、これは訳が分かりませんね。ちょっと解読してみましょう。
+
+先ず、Cont とか runCont とか邪魔なのでなるべく見ないことにしましょう。そうすると (>>=) の方は Monad a に対して::
+
+  Cont a b        -> (b ->   Cont a c     ) -> Cont a c
+  ((b -> a) -> a) -> (b -> ((c -> a) -> a)) -> ((c -> a) -> a)
+
+こうなってるはずです。というわけで::
+
+  m :: (b -> a) -> a
+  k :: b -> (c -> a) -> a
+
+と思って無理矢理組み合わせてみようとすると::
+
+                   k        ::              b -> ((c -> a) -> a) -- これは与えられてる
+           \x ->   k x      ::              b -> ((c -> a) -> a) -- lambda で書いてみる
+                   k x      ::                    (c -> a) -> a  -- (c -> a) を適用したい!
+  \y ->   (\x -> ((k x) y)) :: (c -> a) -> (b ->              a) -- (c -> a) もってきて適用
+           \x -> ((k x) y)  ::              b ->              a  -- これは m が適用できる!
+  \y -> m (\x -> ((k x) y)) :: (c -> a) -> a                     -- (b -> a) に m 適用
+
+材料の型だけ見て、どうやらこう定義するのが良さそうに見えてきました。あとは Cont と runCont で飾ってあげれば定義になります。でもこれ何してるんだ? 簡単な例でも考えてみましょうか。
+
+m は return x にしましょう、x :: b と思って。k は、f :: b -> c と思って k = return . f でどうでしょう? そうすると?::
+
+  m >>= k
+  = \z -> (return x) (\w -> ((return . f $ w) z))
+  = \z -> ($ x) (\w -> ($(f w)) z)
+  = \z -> ($(f x)) z
+  = \z -> z (f x)
+
+なんと、っていうかこんなの計算しなくてもこれ Monad らしいんだから::
+
+  m >>= k = (return x) >>= return . f = return (f x)
+
+って Monad 則から直ぐなのではっ!
+
+m =「x を代入」を k=「f したものを代入」に通したので「f x を代入」になりました。まんまですね。
 これで Monad のこともばっちりだね!!
 -----------------------------------