継続モナドについて

# 継続モナド

　継続渡しスタイルの関数をモナドのインスタンスにしたもの。Haskellで書くと以下のようなもの。

```Haskell
newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }
```

　これを用いると、Haskellのモナドに対する手厚いサポートを受けながら、継続渡しスタイルの恩恵を受けることができる。

## もくじ

1. 継続モナドとは？
1. 継続モナドを使う
1. 継続モナドとリソース管理
1. 継続モナドとcallCC


## 継続モナドとは？

　継続モナドのHaskellコードを再掲する。分かりやすくするため、基底モナドの部分を削っている。

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

　`(a -> r) -> r`は、継続渡しスタイルの関数を一般化した型だ。
　単に`a`と書けばいいところを、わざわざその値を使った関数を受け取って適用するところまで面倒を見ている。
　このような形で書くと、関数呼び出しを単にジャンプに置き換える最適化をすることができたり、不要なパターンマッチを減らすことができるなどの恩恵を受けられる場合がある。また、コンパイラが最適化の一環としてコードを継続渡しスタイルに変換することもあるらしい。

### 継続渡しスタイルとは？

　ところで、継続渡しスタイルとはなんだろう。
　まずは具体例を見ていこう。下は、`(+)`を継続渡しスタイルに直した関数だ。接頭辞`cps`はcontinuation passing styleの略であり、継続渡しスタイルを意味している。

```Haskell
cpsSum :: Int -> Int -> (Int -> r) -> r
cpsSum m n f = f $ m + n
```

　通常の関数としての処理をした後に、それを使った処理（継続）`f`を適用する形になっている。その関数の呼び出し後の処理（継続）を受け取って、それを適用してやるところまで面倒を見るのが継続渡しスタイルの特徴だ。
　最も単純な形は、下のような値を継続渡しスタイルに直したものになるだろう。例えば、`cpsSum 10 20`という式の型は、`(Int -> r) -> r`となる。

```Haskell
cpsVal :: (Int -> r) -> r
cpsVal f = f 30
```

　継続渡しスタイルで少し遊んでみよう。下のような、値を継続渡しスタイルの値に変換する関数を作成する。

```Haskell
mkCps :: a -> (a -> b) -> b
mkCps a f = f a
```

　これらを使って、継続渡しスタイルを使って値を作成する一連の流れを作ることができる。最後の`id`は何もしない継続であり、唯一継続渡しスタイルではない関数だ。

```Haskell
>>> cpsVal $ \a -> cpsSum a 1 $ \b -> mkCps (b + 2) id
33
```

　ところでこの継続渡しスタイル、ケラー脳を働かせて目を細めてみると、段々`$`が`>>=`に見えてこないだろうか？

### 継続渡しスタイルをモナドのインスタンスにする

　前置きはこの辺にして、`ContT`をモナドのインスタンスにしていこう。

```Haskell
newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }

instance Monad (ContT r m) where
    return a = ContT $ \f -> f a
    ContT a >>= f = ContT $ \g -> a $ \a' -> runContT (f a') g
```

　`return`の中でやっていることは、まさに値を継続にする関数`mkCps`だ。`return = ContT . mkCps`と書き換えてもよい。
　bindの中では、古い継続`a`に関数`f`を適用して、それに新しい継続`g`を添えてやっている。`a $ \a' -> ..`のくだりは、継続渡しスタイルの例でも見た、ある継続に次の継続を継ぎ足してやるときのお決まりの構造だ。

　`Functor`や`Applicative`は面倒なので手抜きの実装をしてしまおう。これで正式にモナドのインスタンスになった。

```Haskell
instance Functor (ContT r m) where
    fmap = liftM

instance Applicative (ContT r m) where
    pure = return
    (<*>) = ap
```

　ついでにモナディックではない値を扱いやすくするエイリアスを作ろう。

```Haskell
type Cont r a = ContT r Identity a

cont :: ((a -> r) -> r) -> Cont r a
cont f = ContT' $ Identity . f . fmap runIdentity

runCont :: Cont' r a -> (a -> r) -> r
runCont c f = runIdentity $ runContT c (Identity . f)
```


## 継続モナドを使う

　継続渡しスタイルをモナドのインスタンスに落とし込むことが何を意味するかといえば、「値を継続渡しスタイルにする」「継続渡しスタイルの関数に継続渡しスタイルの関数を継ぎ足す」という継続渡しスタイルの特徴を、モナドのメソッドに抽出することができたということだ。
　上でやった継続渡しの例を、モナドを使って書き直してみよう。

```Haskell
-- 生の継続渡し
>>> cpsVal $ \a -> cpsSum a 1 $ \b -> mkCps (b + 2) id
33

-- 継続モナドを使った継続渡し
>>> runCont (cont cpsVal >>= \a -> cont (cpsSum a 1) >>= \b -> return (b + 2)) id
33
```

　見た目がそっくりであることが分かるだろう。というのも、やっていることが各継続渡しスタイルの関数をラップして、最後にラップを剥がすだけなのだ。`return`は`ContT . mkCps`であるため、これを書き換えている。
　`>>=`で繋げているということは、`do`文で書き下せるということだ。下のコードは、上の継続モナドを使った継続渡しと全く同等のコードである。

```Haskell
>>> flip runCont' id $ do
>>>     a <- cont' cpsVal
>>>     b <- cont' $ cpsSum a 1
>>>     return $ b + 2
33
```

　継続渡しの読みづらさが消えて、慣れ親しんだ形になった。これで、慣れ親しんだ構文と継続渡しのメリットが両立されることになった。

## 継続モナドとリソース管理

　私は、継続モナドが最も役に立つ場面は、リソース管理だと思っている。ここでは継続モナドを用いたリソース管理方法を紹介しよう。
　ここでのリソース管理は、`open`/`close`と対になった関数があって、`open`したリソースは`close`しなければならないアレだ。一番わかりやすいのはファイル操作だろう。
　Haskellでは、ファイルのオープン/クローズは以下のような関数を使う。これを使って、オープンしたハンドルを間違いなく閉じる関数を考えよう。

```Haskell
openFile :: FilePath -> IOMode -> IO Handle
hClose :: Handle -> IO ()
```

　`handle`を使う処理を引数に抜き出せば、こんな関数になるはずだ。この関数を使えば、どの二つの関数が対になっているかを考える必要はないし、`hClose`が間違いなく実行されることが保証される。

```Haskell
withFile :: FilePath -> IOMode -> (Handle -> IO ()) -> IO ()
withFile filePath mode processHandle = do
    handle <- openFile filePath mode
    processHandle handle
        `finally`
        hClose handle
```

　ところで、この関数は部分適用すると`(Handle -> IO ()) -> IO ()`という型になることが分かる。これは継続渡しの型そのものではないか！
　さっそく継続モナドを使ってファイルリソース管理を行う処理を書いてみよう。
　下は、継続モナドを使ってファイルコピーをする例だ。特別なことをしてるようには見えないが、二つのファイルを開き、そのいずれもが正しく閉じられることが保証されている。

```Haskell
copyFile :: String -> String -> ContT () IO ()
copyFile srcFilePath destFilePath = do
    hSource <- ContT $ withFile srcFilePath ReadMode
    hDest <- ContT $ withFile destFilePath WriteMode
    content <- liftIO $ hGetContents hSource
    liftIO $ hPutStr hDest content
```

　そういうわけで、`System.IO.withFile`には全く同じ関数が用意されている。他にも対になる関数でリソース獲得/解放を提供するライブラリは`with*`という命名の関数を用意していることが多い。

## 継続モナドとcallCC

### 継続の破棄

　継続渡しスタイルの関数は、引数に渡された継続に値を詰めて流す。それでは、もし値を継続に渡さなかったらどうなるだろうか？

```Haskell
>>> mkCps (0 :: Int) $ \a -> cpsSum a 1 $ \b -> mkCps (b + 2) id
3
>>> const (0 :: Int) $ \a -> cpsSum a 1 $ \b -> mkCps (b + 2) id
0
```

　`const 0`は、引数に何をもらっても`0`を返す関数だ。すなわち、引数にどのような継続をもらっても`0`を返す。
　これは継続渡しスタイルの言い方をすれば、途中で継続を破棄してしまうということだ。これは、手続き的には関数の途中で`return`をしてしまったり、あるいは例外が投げられた時のような状況が連想される。
　`Cont`モナドを使うコードでは、以下に対応する。`const`に渡した値が最終的な値となり、以降の継続が破棄される。

```Haskell
>>> flip runCont id $ do
>>>     n <- cont $ const 2
>>>     return $ 10 + n
2
```

　見ての通り、無条件に継続を破棄してしまうだけで、あまり役に立たない。そこで、現在の継続を渡して呼び出し、継続が終了した時点での継続を引き継ぐことができるような関数を考える。

```Haskell
callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a
callCC f = ContT $ \g ->
    runContT (f $ ContT . const . g) g
```

　`ContT . const . g`の部分に、継続の破棄が表れている。`g`は`callCC`を呼んだ後の継続であり、`f`の引数である`exit`を呼びだした時にその時点で残りの継続を破棄する。
　さっそく使ってみよう。

```Haskell
>>> flip runCont id $ do
>>>     n <- callCC $ \exit -> do
>>>         exit 2
>>>         return 3
>>>     return $ n * 5
10
```

　`exit`の時点で継続を打ち切り、`callCC`の外へと処理が飛んでいるのが分かる。
　ここで`const`を使ったらどうなるだろうか？

```Haskell
>>> flip runCont id $ do
>>>     n <- callCC $ \exit -> do
>>>         cont $ const 2
>>>         exit 3
>>>     return $ n * 5
2
```

　なるほどね。

### 継続の取り出し

　ところで、こんな化け物のような関数を定義することができる。

```Haskell
getCC :: ContT r m (ContT r m a)
getCC = callCC $ \exit ->
    let a = exit a
     in return a
```

　これを使うと、継続を取り出すことができる。取り出した継続は、文字通りその後の継続であるため、これを継続に加えると事実上のループを作ることができる。
　下は、標準入力から"bye"を受け取るまで処理を繰り返す例だ。

```Haskell
do  goto <- getCC
    line <- lift getLine
    lift $ putStrLn line
    when (line /= "bye")
        goto
```

　また、継続を実行した後の値を同時に返すように改変することができる。

```Haskell
getCC' :: a -> ContT r m (a, a -> ContT r m b)
getCC' a = callCC $ \exit ->
    let f b = exit (b, f)
     in return (a, f)
```

　これはより分かりやすい例を提供する。

```Haskell
do  (x, goto) <- getCC' 0
    lift $ print x
    when (x < 10) $
        goto $ x + 1
```

　継続渡しによるループからは、最適化された末尾再帰を直接実装しているような印象を受ける。
　このように、継続をオブジェクトとして引き回す力を持つ`callCC`は、`MonadCont`型クラスのメソッドにもなっている。

```Haskell
class MonadCont m where
    callCC :: ((a -> m b) -> m a) -> m a
```

## まとめ

　継続渡しスタイルとそれをモナドにした`ContT`、これを利用したリソース管理の方法、そして継続という考え方の応用である`callCC`について勉強した。継続は制御構造を一般化したもの（らしい）ので、条件分岐や例外、ループをも再現することができる。
　本当はreset/shiftについても書きたかったが、力尽きたのでここまで。

　それではさようなら。

## 参考文献

継続渡しなHaskellライフ
http://fumieval.hatenablog.com/entry/2014/02/11/205916

shift/reset プログラミング入門
http://pllab.is.ocha.ac.jp/~asai/cw2011tutorial/main-j.pdf

Compose
https://wiki.haskell.org/Compose