Contモナドとcall/cc

前回:

前回で継続の説明と継続渡しを暗黙的に行うContモナドが作れたので，今回はcall/ccの実装を行います．

call/ccとは

継続の代名詞であるSchemeには，call-with-current-continuation略してcall/ccという関数があります．この関数は「引数として渡された関数に，現在の継続を渡して実行する」という関数です．前回定義したContモナドを使った例で言うと，次のような雰囲気の関数になります．

someAction :: Cont result a
someAction = do
  x <- callCC $ \cont -> do
    -- cont は，... 以降の計算を表す継続になる
    OOO
    XXX
  ...

ここで，例えば内側のdoブロックの内部でcont hogeなどと実行すると，callCCの呼び出し時点での継続にhogeが引数として与えられます．すなわち，cont hogeが実行された時点でsomeActionの1行目に戻り，xの値がhogeで束縛された状態で，...以降の実行へ移ります．

また，内側のdoブロックの内部でcontが一度も呼ばれずにreturnした場合，返ってきた値がそのままxに束縛されて...以降の実行へ移ります．

実装

先ほど書いたとおり，このcallCCの使い方は以下のようになります．

x <- callCC (\cont -> ...)

ここで，xの型がaであり，最終的な実行結果の型がresultであるとすると，先ほどの説明によりそれぞれのコード片の型は以下のようになります．

x :: a
callCC (\cont -> ...) :: Cont result a
cont :: a -> 何か
(\cont -> ...)の戻り値 :: Cont result a

contはこれまでの意味だと「最終的な実行結果までの計算」を表すためa -> resultでした．しかし，これをそのまま使うとこのcontをContモナドの中に埋め込めなくなってしまいます．そこで，この文脈では少し型をいじって，a -> Cont result bになるようなcontを渡すことにしましょう．すると，

cont :: a -> Cont result b
(\cont -> ...) :: ((a -> Cont result b) -> Cont result a)

と書くことができます．これらをまとめると，callCCの型は以下のようになります．

callCC :: ((a -> Cont result b) -> Cont result a) -> Cont result a

次に，具体的な実装を考えていきましょう．先ほどの例をもう一度挙げます．

someAction :: Cont result a
someAction = do
  x <- callCC $ \cont -> do
    -- cont は，... 以降の計算を表す継続になる
    OOO
    XXX
  ...

内側のdoブロックの中でcontが呼ばれた場合，その時点での継続を破棄して外側の...の部分が呼ばれるのでした．外側の部分の継続がouterContという名前で与えられているとすると，このcontは次のような式になるはずです．

cont = \a -> Cont $ \_innerCont -> outerCont a

これを踏まえると，callCCの実装は以下のようになります．

callCC f = Cont $ \outerCont ->
  runCont (f $ \a -> Cont $ \_innerCont -> outerCont a) outerCont

call/ccを使ってみる

それでは，たった今完成したcallCCを使ってみましょう．

example :: Cont result Int
example = do
  x <- callCC $ \xCont -> do
    xCont 3
    return 4
  y <- callCC $ \yCont ->
    return 5
  return $ x + y

このexampleを実行した結果がどのようになるかわかるでしょうか？

1つ目のcallCCの内側では，xContに3を渡しているため，その時点で内側のdoブロック内部での継続は破棄され，x <- ...の部分の継続に処理が戻ります．それに対して，2つ目のcallCCの内側では，yContを呼ばずに単に5を返しているため，それが通常通りyに渡され，exampleの返す値は3 + 5 == 8になります．

*Cont> :l Cont
[1 of 1] Compiling Cont             ( Cont.hs, interpreted )
Ok, modules loaded: Cont.
*Cont> runCont example id
8

慣れていないと分かりにくいかもしれませんが，これを応用すると面白いものが書けます．

応用例: ループからbreak

[Maybe Int]を受け取り，Just xの形の要素だけの和を取る関数sumJustを考えてみます．この場合は必要ありませんが，今後の拡張のためこの関数はContモナドに包まれるように定義します．

sumJust :: [Maybe Int] -> Cont result Int
sumJust xs = foldM iter 0 xs
  where
    iter acc (Just x) = return $ x + acc
    iter acc Nothing = return acc

実行結果:

*Cont> runCont (sumJust [Just 1, Just 2, Just 3, Nothing, Just 4, Nothing, Just 5]) id
15

1 + 2 + 3 + 4 + 5 == 15です．

次に，この関数を少し書き換えて，最初にNothingが出て来るまでの値の和を求めるようにしましょう．callCCを使うと，あたかもNothingが出てきた時にループをbreakするかのように処理を書くことができます．

sumTillNothing :: [Maybe Int] -> Cont result Int
sumTillNothing xs = callCC $ \break -> foldM (iter break) 0 xs
  where
    iter _ acc (Just x) = return $ x + acc
    iter break acc Nothing = break acc

実行結果:

*Cont> runCont (sumTillNothing [Just 1, Just 2, Just 3, Nothing, Just 4, Nothing, Just 5]) id
6

このように，継続をうまく扱うことで，トリッキーな処理を実装することができるようになります．

使い所は限られるかもしれませんが，場合によっては素直に書くと複雑になってしまうような処理を簡単に書くことができるかもしれません．

call/ccとは

実装

call/ccを使ってみる

応用例: ループからbreak

関連記事