2012年2月18日土曜日

手計算で monad を理解してみる

去年の秋頃から、暇なときにちょこちょこ Haskell をいじっているけど実に面白い。

やっぱり一番おいしいところは、Monad をはじめとする計算のやり方なんだろうけど、一行に収まるくらいの短い式を書いて、手書きで計算してみると意外と理解に役立つ事に気がついた。

例えば、runCont (return "hello") (++"!") を計算すると "hello!" になるけど、たぶん慣れてる人には自明過ぎるようなこんな計算でも、初めての時は何だか分かったような分かってないようなあやふやな感じがする。

これをこんな風に手計算してみる。(関数等の定義は「All About Monads」のここを参考にした。)

runCont (return "hello") (++"!")
= runCont(Cont $ \k->k "hello")) (++"!") … ①
= (\k->k "hello")) (++"!") … runCont の定義より
= (++"!") "hello"
= "hello!" 

① return の定義、return a = Cont $ \k -> k a より
個人的には、これであやふやな感じが解消してスッキリする。

続けて更に Cont から別の例を出してみると、callCC なんかも下の定義だけだは、何がどうなるのかよく分からない。
callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

この辺りのサンプルコードを読むと、使い方が何となく分かるが、どういう仕組みでそうなるのか腑に落ちずモヤモヤする。

例えば 「runCont (callCC (\ex -> do {ex "bye"; return "hi"})) (++"!") 」みたいな式で、なんで "hi!" にならないのか不思議だったりする。

こんなのも手で計算してみると、細かいところがはっきりする。

  runCont (callCC (\ex -> do {ex "bye"; return "hi"})) (++"!")
= runCont (callCC (\ex -> ex "bye" >>= (\f -> return "hi"))) (++"!")
= runCont (Cont $ \k -> (\_ -> (k "bye")) k) (++"!") … (a)
= (\k -> (\_ -> (k "bye")) k) (++"!")
= (\_ -> ((++"!") "bye")) (++"!")
= (++"!") "bye"
= "bye!"

(a)
callCC f = Cont $ \k-> runCont (f(\a-> Cont $ \_->k a)) k より

  callCC (\ex->ex "bye">>=(\f->return "hi"))
= Cont $ \k-> runCont ((\ex -> ex "bye">>=(\_ -> return "hi")) (\a-> Cont $ \_ -> k a)) k
= Cont $ \k-> runCont (((\a -> Cont $ \_ -> k a) "bye") >>= (\_ -> return "hi")) k
= Cont $ \k-> runCont ((Cont $ \_ -> k "bye") >>= (\_ -> return "hi")) k
= Cont $ \k-> runCont (Cont $ \_ -> (k "bye")) k … (b)
= Cont $ \k-> (\_ -> (k "bye")) k

(b)
(Cont c) >>= f = Cont $ \k' -> c (\a -> runCont (f a) k') より

  (Cont $ \_->k "bye") >>= (\_ -> return "hi")
= Cont $ \k' -> (\_ -> k "bye") (\a -> runCont (f a) k')
= Cont $ \_ -> (k "bye")

実は最初、遅延評価に変にこだわってしまって手こずっていたんだけど、参照透明なんだから好きな順序で計算しても結果は変わらないわけで、手計算のときは余り気にする必要が無いと開き直って簡単になった。

0 件のコメント:

コメントを投稿