Haskellの継続モナド(Continuation Monad)を理解するポイント

モナドのすべて継続モナドのところが簡潔で、概念とかもあまり明示的に説明してなくて理解に苦労したので、ポイントをメモ。誤りなど、乞うご指摘。

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

概要的なこと

継続といいつつ、Contが表すのは継続というより、CPSな関数。*1

  • CPSな関数は、引数に関数をとり、自分の仕事の最後でその関数(継続)を呼ぶ。
  • CPSな関数に、継続として別のCPSな関数を渡す、その別のCPSな関数に継続としてさらに別のCPSな関数を渡す、…の連鎖(CPSな関数のネスト)が、全体としてCPSなプログラム。
  • 継続モナドでは、CPSな関数をContにくるんで >>= で繋ぐことで↑を実現できるようにしてある。

Contの定義

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) }

  • runContが、そのCPSな関数。
  • つまり、引数に継続の関数(a->r)を取って、最後にその継続を呼ぶ(から継続の返値rが、この関数の返値r)
  • 動かすときは、runCont自体を呼ぶ。

bind関数(>>=)

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

  • c >>= f は、cに継続fを渡すのが仕事であるCPSな関数(をContでくるんだもの)。つまり、引数に継続の関数kをとり、cしてfしてkするCPSな関数(をContでくるんだもの)。
  • 「runCont (f a) 」の部分: f aが、CPSな関数をContにくるんだのを返す。runContでそのCPSな関数を取り出される。
  • 「runCont (f a) k」の部分: ↑に継続の関数としてkが渡される。つまり、f aは仕事の最後にkを呼ぶ。「faしてk」
  • 「c (\a -> runCont (f a) k)」 の部分: cはCPSな関数。それに対して、継続の関数として「a->faしてk」が渡される。cの仕事の最後で「a->faしてk」が呼ばれる。
  • 「\k -> c (\a -> runCont (f a) k)」 の部分: kを継続の関数として引数にとり、「cが最後にfを引数aで呼び、fは最後にkを呼ぶ」という、CPSな関数。
  • 結局、cしてfしてkする*2CPSな関数が合成された。それをContでくるんである。
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

Call with Current Continuation

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

  • callccといいつつ、環境をキャプチャしたりせず、単にCPS連鎖でそれ以降をスキップするだけ。*3
  • fの継続はkだが、f自身の中でもう一階層下に継続連鎖を持っている事が前提。下の階層の継続連鎖から好きなとき(fの引数を呼ぶ)にkにジャンプするために使う。
  • 「(\a -> Cont $ \_ -> k a)」の部分: aを引数に取り、継続の関数として渡された関数をシカトして、k aを返すニセのCPSな関数(をContでくるんだもの)を返す関数。ニセのCPSな関数に継続の(CPSな)関数を渡すと、渡された関数以降の継続連鎖(CPSな関数のネスト)はスキップされk aが値となる。
  • 「(f (\a -> Cont $ \_ -> k a))」の部分: fは「CC(callCCの時点の継続)」を引数に渡して貰いたい関数。fがこの↑の「CC」を引数aで呼び出すと、「以降の継続連鎖(CPSな関数のネスト)はスキップされk aが値となる」ニセCPSな関数をContでくるんだモノになる。
  • 「\k -> runCont (f (\a -> Cont $ \_ -> k a)) k」の部分: 継続の関数kを引数にとり、ニセのCPSな関数\_ -> k aをContで来るんだものを返す、CPSな関数。
  • 結局、(ニセのCPSな関数(をContでくるんだもの)を生む)CPSな関数が合成された。それをContでくるんである。


でも、よい子は継続モナドは使っちゃダメだそうで。なのに、合成モナドの説明が継続モナドを例に使ってるので、しかたなく理解を試みた次第。

*1:ただ、そのCPSな関数自体を、継続として他のCPSな関数に渡す使い方をするので、その意味で継続であるとは言える

*2:cもfもちゃんと継続の関数を最後に呼ぶ限り

*3:callCC時点での、CPS連鎖の「次」を「現在の継続」として擬似的にキャプチャとは言えるかも