無限ループから抜け出すプログラム

Haskell は簡単に無限ループを作れる。
もちろん他の言語でも`while(1)`とすれば簡単に作れるけど、じゃあその無限ループから脱出する`break`に相当する機能をHaskellでも作れるだろうか。

(｀･ω･´)

実際に作ってみた。

```hs:Main.hs
import Control.Monad.Cont

main :: IO ()
main = do
 putStrLn "Start"

 withBreak $ \break ->
 forM_ [1..] $ \i -> do
 liftIO . putStrLn $ "Loop: " ++ show i
 when (i == 5) $ break ()

 putStrLn "End"
 where
 withBreak = flip runContT pure . callCC
```

```bash
$ runhaskell Main.hs
Start
Loop: 1
Loop: 2
Loop: 3
Loop: 4
Loop: 5
End
```

大事なのはこの部分

```hs
withBreak $ \break ->
 forM_ [1..] $ \i -> do
 liftIO . putStrLn $ "Loop: " ++ show i
 when (i == 5) $ break ()
```

気持ちはこんな感じ

```cpp
int i = 0;
while (1) {
 i++;
 printf("Loop: %d\n", i);
 if (i == 5) break;
}
```

`withBreak`は独自定義なので後で解説する。`forM_`は

```hs
forM_ :: (Monad m) => [a] -> (a -> m b) -> m ()
forM_ = flip mapM_
```

大体こうなっていて単に`mapM_`の引数をひっくり返したものである。`liftIO`は`withBreak`の中で`IO`を使うためのおまじないで`when`は第一引数の条件が満たされた時だけ第二引数を実行する。

`forM_`に渡されているリストは`[1..]`となっていて確かに無限リストなのだが実行結果をみると`break`で処理は終わっている。

`withBreak`を見ていく。

```hs
withBreak = flip runContT pure . callCC
```

大事なのは`runContT`と`callCC`の２つ。

```hs
runContT :: ContT r m a -> (a -> m r) -> m r
callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a
```

`ContT`は継続モナドと呼ばれるもので簡単に言うと後続する計算を扱うことが出来るモナド。継続に関しての詳しい説明は以下の文献を参考にしてください。

* [なんでも継続](http://practical-scheme.net/docs/cont-j.html)
* [継続モナドによるリソース管理](http://qiita.com/tanakh/items/81fc1a0d9ae0af3865cb)
* [Haskell/Continuation passing style](https://en.wikibooks.org/wiki/Haskell/Continuation_passing_style)
* [Control.Monad.Cont](https://hackage.haskell.org/package/mtl/docs/Control-Monad-Cont.html)

実は`withBreak $ \break -> ...`の`break`は後続する計算をただ捨てているだけなのだ。
ここでは`withBreak`をさらに分解して何が起きているのかを理解することにする。まず`ContT`は

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

この様に定義されていて、要するに`(a -> m r) -> m r`だ。`callCC`の実装は

```hs
callCC :: ((a -> ContT r m b) -> ContT r m a) -> ContT r m a
callCC f = ContT $ \ c -> runContT (f (\ x -> ContTr) -> (a -> m r) -> m r
callCC f c = f (\x _ -> c x) c
```

こうなる。型は複雑になったが実装はとても簡単だ。これを使うと`withBreak`は

```hs
withBreak :: ((a -> (b -> m r) -> m r) -> (a -> m r) -> m r) -> m r
withBreak f = f (\x _ -> pure x) pure
```

となる。最初のプログラム中で`f`に対応するものは`\break -> ...`の部分である。ここで初めて`break`は

```hs
break :: a -> (b -> m r) -> m r
break = \x _ -> pure x
```

のようなものであることがわかった。

もう一度継続モナドに戻る。`ContT`のモナドの実装は

```hs
instance Monad (ContT r m) where
 return x = ContT ($ x)
 m >>= k = ContT $ \c -> runContT m (\x -> runContT (k x) c)
```

このようになっていて`(>>=)`を`(a -> m r) -> m r`に合わせて書き直すと

```hs
(>>=) :: ((a -> m r) -> m r) -> (a -> ((b -> m r) -> m r)) -> (b -> m r) -> m r
m >>= k = \c -> m (\x -> (k x) c)
```

また型は複雑になったが実装は読みやすい。実装を眺めるとまず`k`を評価してからその値を使って`m`を評価しているように見える。

準備が整ったので具体的に`break`の挙動を見るために以下のような式を考える。

```hs
actionA >> break () >> actionB
```

まず左側の`>>`を展開する

```hs
(\c -> actionA (\_ -> break () c)) >> actionB
```

次に`break`を展開してみる

```hs
(\c -> actionA (\_ -> pure ()) >> actionB
```

この時点で後続する計算`c`が消えていることがわかる。
最後に残った`>>`を展開する

```hs
\c -> actionA (\_ -> pure ())
```

`actionB`は綺麗に消えてしまった。

最初のプログラムに戻ろう。

```hs
withBreak $ \break ->
 forM_ [1..] $ \i -> do
 liftIO . putStrLn $ "Loop: " ++ show i
 when (i == 5) $ break ()
```

すでに見たように`i`が5に達して`break`が評価された時点で後に続く無限の計算は捨てられていたのである