HaskellのContinuation Monadを理解する(2)

おもむろに・・・

前回に続いて、Continuation Monadと組み合わせて使用する、関数callCCを解説します。

前回作成したCont型（Continuation Monad）と関数pythagoras2を再掲します。

cps.hs

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

instance Monad (Cont r) where
    return x = Cont (\k -> k x)
    m >>= f = Cont (\k -> runCont m (\x -> runCont (f x) k)) 

infixr 5 =:
(=:) :: a -> (a->b) -> b
x =: f = f x 

squareCont x = Cont (\k -> k (x * x)) 
addCont x y = Cont (\k -> k (x + y)) 

pythagoras2 :: Int -> Int -> Cont r Int 
pythagoras2 n m = do
    x <- squareCont n
    y <- squareCont m
    result <- addCont x y
    return result

ここで、さらに次ような関数pythagoras3を考えてみます。

cps.hsに追加

pythagoras3 :: Int -> Int -> Cont r Int 
pythagoras3 n m = do
    if (n < 0 || m < 0) then return (-1)
                        else do
                            x <- squareCont n
                            y <- squareCont m
                            result <- addCont x y 
                            return result

これは、引数のどちらかが負の数の場合は、平方和の代わりに「-1」を返すように修正したものです。間違いではありませんが、doの2段ネストがあまり美しくはありません。仮に、doの処理を途中で打ち切る「break文」が存在したならば、次のように書き直せそうです。

pythagoras3' :: Int -> Int -> Cont r Int 
pythagoras3' n m = do
    if (n < 0 || m < 0) then return (-1); break
                        else return 0 -- dummy
    x <- squareCont n
    y <- squareCont m
    result <- addCont x y 
    return result

もちろん、do記法は「手続き処理」風な表記にすぎませんので、このような処理は不可能です。しかしながら、関数callCCを使用すると、これに近い書き方ができるようになります。

cps.hsに追加

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

pythagoras4 :: Int -> Int -> Cont r Int
pythagoras4 n m = callCC $ \brk -> do
        if (n < 0 || m < 0) then brk (-1)  -- break
                            else return () -- dummy
        x <- squareCont n
        y <- squareCont m
        result <- addCont x y
        return result

なかなか不思議な動きです。もう少し理解しやすいように、「喰い付き演算子」=:を使って、callCCの定義を次のように変形してみます。

callCC :: ((a -> Cont r b) -> Cont r a) -> Cont r a
callCC f = Cont $ \k -> k =: runCont (stopper k =: f)
        where stopper :: (a -> r) -> (a -> Cont r b)
              stopper k = \a -> Cont (\_ -> k a)

まず、「callCC f」の実行結果は、「Cont $ \k -> k =: c」という形式ですので、「関数kを受け取って、kでcを評価した結果を返す」という意味で普通にContinuation Monadです。次の実行例を考えると、printでcを評価した結果として、89が表示されています。

$ ghci cps.hs
*Main> print =: runCont(pythagoras4 5 8)
89

つまり、「print =: c」で表示される値が「callCC f」に包まれた実質の「値」になります。cの定義に戻ると、これは、次のように解釈できます。

print =: c 
    where c = \k -> k =: runCont (stopper k =: f)
<==> print =: runCont ((stopper print) =: f)
<==> 「(stopper print) =: f」の「中身」をprintに喰わせる

すなわち、Continuation Monad「(stopper print) =: f」の中身こそがその正体です。この実体をゆっくり考えてみましょう。

まず、callCCの引数である「f」は、pythagoras4の例から分かるように「\brk -> do・・・」という形式の関数です。この関数に「(stopper print)」を代入するのが「(stopper print) =: f」の意味ですので、「do・・・」以下に含まれる「brk」は、「(stopper print)」に置き換えればよいわけです。先の例では、「brk (-1)」は、「(stopper print) (-1)」になります。

また、「do・・・」以下は、Continuation Monadの結合計算である事に注意します。callCCの型を見ると、fの型は「(a -> Cont r b) -> Cont r a」ですので、\brkに「(a -> Cont r b)」型の「stopper k」を代入した後の「do・・・」以下は「Cont r b」型を出力するContinuation Monadの結合演算になります。

従って、「brk (-1)」、すなわち「(stopper print)(-1)」は、この結合演算に参加するContinuation Monadの1つである点に留意しつつ、これに「stopper」の定義を代入してみましょう。

(stopper print)(-1)
==> (\a -> Cont ( \_ -> print a ))(-1)
==> Cont (\_ -> print (-1))

さて、結論が見えたでしょうか？

通常のContinuation Monadは、「Cont (\k' -> k'の関数)」という形式の関数であり、この関数の連鎖がContinuation Monadの結合演算にほかなりません。しかしながら、「(stopper print)(-1)」は、連鎖の引数を（\_で受けることによって）無視して、「print (-1)」を吐き出します。つまり、do以下の結合演算の結果は、ここで「print (-1)」に確定します。

・・・と言われてもピンとこない場合は、前回説明したContinuation Monadの結合演算「>>=」の定義に戻ってください。

m >>= f = Cont (\k -> (\x -> k =: runCont (f x) =: runCont m)

「m >>= f」は、「runCont m」を評価する関数として、「\x -> k =: runCont(f x)」という関数を使うということですので、仮にmが「何で評価されようとそれを無視して決まった値を返す」という動きをすると、それ以降のfは何であろうと結果は同じです。いまの場合、mとして、前述の「何で評価されようとprint (-1)を返す」という動きをする「(stopper print)(-1)」が入り込むわけです。つまり、callCCは、「演算の評価を途中で確定させるMonad」を差し込むことで、「break文」と同等の動きを実現しているわけです。

結論だけを考えると、一瞬、callCCような複雑な定義は不要な気がするかも知れません。普通のContinuation Monadのdo表記の中に「Cont(\_ -> 「結論」)」という表現を直書きすればOKな気がします。しかし、この作戦はうまくいきません。今の例では、callCCを「printに喰わせる」という前提で考えたので、差し込むMonadは、具体的に「Cont (\_ -> print (-1))」と確定しますが、実際には、callCCをどのような関数に喰わせるのかは決まっていません。値を評価する関数を具体的に決めずに、引数で受け取る状態、つまり「関数待受状態」こそがContinuation Monadの本質なのですから。

もう一度、callCCの定義を見てみましょう。

callCC f = Cont $ \k -> k =: runCont (stopper k =: f)
        where stopper :: (a -> r) -> (a -> Cont r b)
              stopper k = \a -> Cont (\_ -> k a)

callCCでは、評価する関数を仮引数「\k」で受けて、それを使って「Cont (\_ -> k a)」という「結果確定Monad」をダイナミックに構成した上で、「stopper k =: f」によってf内部の「brk」に代入する、という作戦をとっていることが理解できます。