HaskellのContモナドに触れてみる

Real World Haskellの消化速度が落ちてきたので、息抜きにContモナド(=継続)の解説を読んでみる。
(たぶん、RWH本編には、Contモナドは出てこない。)

"Continuation モナドの濫用は理解や保守が不可能なコードをつくり出す 可能性があります."と書いてあるけど、とりあえず読む。

定義

 newtype Cont r a = Cont { runCont :: ((a -> r) -> r) } -- r は計算全体の最終の型
  
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) 

Haskellの継続は、Monadの形にまとめられている。
コメントにもある通り、Cont r aという型は、途中の計算の型がaで、最終的にはrの値を返すような計算を表している。

Cont型がラップしているデータの型を見る

runCont :: ((a -> r) -> r)

最初の(a -> r) = gと置き換えると 、(g -> r)という形をしているので、Contがラップしているのは、1引数の関数である。
g = (a -> r) なので、その関数は(a -> r)という型のデータを引数にとる。
この引数 (a -> r)自体も関数で、この関数が継続(=この先の計算)を表現している。(たぶん)
Contデータ型は、継続を引数にとり、"その継続を使って最終的な値を計算する方法"を表現した関数である。

returnと bindの定義を見る

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

return aすると、継続を受け取って、その継続にaを渡すだけの計算が作られる。
(>>=)の定義は若干ややこしい。
右辺

Cont $ \k -> c (\a -> runCont (f a) k)

を見ると、bindした結果は、新しいContになる。(あたりまえ)
その新しいContは、次のような計算を行う。

  1. その時点での継続 k を受け取る。
  2. 合成式の左辺にあった計算cに、継続として(\a -> runCont (f a) k)を渡す
  3. この結果、cの計算の結果は、(\a -> runCont (f a) k)に実引数aとして束縛される
  4. cの計算結果をfに適用し、その結果得られた計算に、継続としてkを渡す

結果的に、

cの計算をして結果aを得る→そのaをつかって新しい計算(f a)を作る→新しくできた計算(f a)に継続としてkを渡し、最終的な計算結果を得る

という計算が合成される。

callCCの定義を見る

class (Monad m) => MonadCont m where 
    callCC :: ((a -> m b) -> m a) -> m a 
 
instance MonadCont (Cont r) where 
    callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k

callCCは、継続cを引数にとるような計算fを引数にとって、Cont型の計算を返す。
fには、第一引数として、継続 c :: (a -> m b)が渡される。
c :: (a -> m b)なので、この継続の最終的な計算結果自体もCont型。
callCCのinstance宣言の定義にあるとおり、fに渡される継続は (\a -> Cont $ \_ -> k a)という計算。
ここでのポイントは、 Cont $ \_ -> k aという式で、これはその時点での継続 '_'を全く無視してcallCCが呼ばれた時点での継続 k のみを使っている。
これにより、fのなかで、cを呼び出すと、計算f中の継続は無視され、callCCが呼ばれた時点での継続に処理が引き継がれる。(=大域脱出)




。。。
たぶんいろいろ間違っているので、指摘していただけるとありがたいです。(なんじゃそら)