日々の流転

どうも。米澤です。興味を持っていただいてありがとうございます。<br>スライドはこちらです。<br>http://www.logic.cs.tsukuba.ac.jp/~yone/ppl_2007/slide.pdf<br><br>例えば、StateモナドとContモナドをモナド変換子を使って合成することを考えます。<br>ContTを使う場合はよいのですが、StateT s (ContT r)という風にStateTを使う場合、<br>StateT s (ContT r)のためのcallCCの定義はlift . callCCでは不十分です。<br>なぜなら、lift . callCCの型は<br><br> ((a -> Cont r b) -> Cont r a) -> StateT s (Cont r) a<br><br>となり、(a -> StateT s (Cont r) b) -> StateT s (Cont r) a型の引数を取れないからです。<br><br>そのため、現状のHaskellでは<br><br> instance (MonadCont m) => MonadCont (StateT s m) where<br> callCC f = StateT $ \s -><br> callCC $ \c -><br> runStateT (f (\a -> StateT $ \s' -> c (a, s'))) s<br><br>などのように既知のモナドそれぞれに対して個別の定義を与えています。<br>これはあまり綺麗な方法ではありません。<br>これをなんとかしようという話です。<br><br><br>ここで、callCCの仕事を詳しく見てみると、<br><br> 1. 継続を捕え、関数にする<br> 2. それを引数に与え、その結果を自分自身の結果とする<br><br>の2つがcallCCの仕事です。<br>しかし、2でやっていることは>>=の仕事と変わらず、callCCの仕事の本質は1のみです。<br>一方、上で挙げた「合成モナドのためのcallCCが綺麗に書けない問題」は2から起きています。<br>そのため、1のみを行う演算子を定義してやれば上の問題は解決できるのではないか、というのがアイデアです。<br><br><br>そこで、<br><br> getCC :: Cont r (Either a (a -> Cont r b))<br> getCC = callCC (\c0 -> return (Right (c0 . Left)))<br><br>という演算子を定義してやります。<br>これは<br><br> do<br> x <- getCC<br> (case x of<br> (Right c) -> foo<br> (Left v) -> bar)<br><br>という風に使います。<br>すると、getCCの継続(の前にLeftが関数合成されたもの)がcに入れられ、<br>fooの部分が実行されます。<br>そしてcを呼び出すとその引数がvに入れられ、barが実行されます。<br><br>ここで、getCCは引数を取らないので、getCCと、cの呼び出しをliftしてやることで、<br>合成モナドでも使えます。<br><br>このgetCCを直接使ってプログラムを書いてもいいのですが、<br><br> genericCallCC :: (Monad m)<br> => (forall d. Cont r d -> m d)<br> -> ((a -> m b) -> m a) -> m a<br> genericCallCC cast body<br> = do<br> x <- (cast getCC)<br> (case x of<br> (Right c) -> body (cast . c)<br> (Left v) -> return v)<br><br>という関数を定義してやると、今まで<br><br> instance (MonadCont m) => MonadCont (StateT s m) where<br> callCC f = StateT $ \s -><br> callCC $ \c -><br> runStateT (f (\a -> StateT $ \s' -> c (a, s'))) s<br><br>と定義していたものを<br><br> instance (MonadCont m) => MonadCont (StateT s m) where<br> callCC = genericCallCC lift<br><br>と置き換えることができます。<br><br>見てのとおり、StateTに依存した部分はないので、任意のモナド変換子に対して同じ定義が使えます。<br>また、castに与える関数を変えることで、モナド変換子以外のモナド合成方法にも対応できます。<br>よって、「合成モナドのためのcallCCが綺麗に書けない問題」は無事解決できました。<br><br>なお、castをliftに決め打ちしてしまって、<br><br> genericCallCC' body<br> = do<br> x <- (lift getCC)<br> (case x of<br> (Right c) -> body (lift . c)<br> (Left v) -> return v)<br><br>と定義すれば、型宣言に表れるforall dは必要なくなるので、Haskell98の範囲で書けます。<br><br><br>この手法をcallCC以外の演算子に適用できないか考えましたが、<br>callCCの性質に依存した部分が多く、汎用性はなさそうです。<br>そういったこともあり、また私の修論テーマとも絡んでこなかったので、<br>PPLで発表した後はそれっきりになってます。

どうも、酒井です。はじめまして。<br>ちょっとした興味だったのに、非常に詳しい説明ありがとうございます。<br>モナド変換子はいまだに苦手なのですが、面白い話だと思いました。

そういえば、今度の Continuation Fest 2008 で発表すると Oleg さん辺りが喜ぶのでははないかと思いました。