Continuation モナド

理解するのにすごく苦労したのでメモ。
まず、定義はこんな感じ。

instance Monad (Cont r) where 
    return a       = Cont $ \k -> k a                       -- i.e. return a = \k -> k a 
    (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k) -- i.e. c >>= f = \k -> c (\a -> f a k) 

http://www.sampou.org/haskell/a-a-monads/html/contmonad.html

runCont

runContの中身が書いてないが、以下のような定義だと思われる。
第1引数にContモナドをとり、中身のcを取り出し、kに適用する。

runCont (Cont c) k = c k

bind

自分としては、>>=の中身は、以下のように2カ所にrunContを使った式の方がわかりやすいと思う。
なお、もとの定義での(Cont c)がccに対応する。

cc >>= f = Cont $ \k -> runCont cc (\a -> runCont (f a) k)

継続渡し→モナド

以上を踏まえて普通に書いた継続渡し版の階乗からモナド版の階乗を導いてみる。

fact 0 k = k 1
fact n k = fact (n - 1) (\a -> k $ n * a)
main = fact 4 print

kを呼び出している部分を(\k -> k ...)に変形する。

fact 0 = \k -> k 1
fact n = \k -> fact (n - 1) (\a -> (\k -> k $ n * a) k)
main = fact 4 print

(\k -> ...)を、Contモナド(Cont $ \k-> ...)にする。
これにあわせて、Contモナドに引数を適用しているところはrunContを介するようにする。

fact 0 = Cont $ \k -> k 1
fact n = Cont $ \k -> runCont (fact $ n - 1) (\a -> runCont (Cont $ \k -> k $ n * a) k)
main = runCont (fact 4) print

(Cont $ \k -> k ...) を (return ...) に置き換える

fact 0 = return 1
fact n = Cont $ \k -> runCont (fact $ n - 1) (\a -> runCont (return $ n * a) k)
main = runCont (fact 4) print

(fact $ n - 1) が cc、(return $ n * a) が (f a) に対応するので、>>=に置き換える。
なお、f a = x のとき、f = \a->x

fact 0 = return 1
fact n = (fact $ n - 1) >>= (\a -> return $ n * a)
main = runCont (fact 4) print

さらにdo記法に変形して完了。

import Control.Monad.Cont
fact 0 = return 1
fact n = do a <- fact $ n - 1
            return $ n * a
main = runCont (fact 4) print