Haskell は簡単に無限ループを作れる。
もちろん他の言語でもwhile(1)とすれば簡単に作れるけど、じゃあその無限ループから脱出するbreakに相当する機能をHaskellでも作れるだろうか。
(｀･ω･´)
実際に作ってみた。
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
$ runhaskell Main.hs
Start
Loop: 1
Loop: 2
Loop: 3
Loop: 4
Loop: 5
End
大事なのはこの部分
withBreak $ \break ->
forM_ [1..] $ \i -> do
liftIO . putStrLn $ "Loop: " ++ show i
when (i == 5) $ break ()
気持ちはこんな感じ
int i = 0;
while (1) {
i++;
printf("Loop: %d\n", i);
if (i == 5) break;
}
withBreakは独自定義なので後で解説する。forM_は
forM_ :: (Monad m) => [a] -> (a -> m b) -> m ()
forM_ = flip mapM_
大体こうなっていて単にmapM_の引数をひっくり返したものである。liftIOはwithBreakの中でIOを使うためのおまじないでwhenは第一引数の条件が満たされた時だけ第二引数を実行する。
forM_に渡されているリストは[1..]となっていて確かに無限リストなのだが実行結果をみるとbreakで処理は終わっている。
withBreakを見ていく。
withBreak = flip runContT pure . callCC
大事なのはrunContTとcallCCの２つ。
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は継続モナドと呼ばれるもので簡単に言うと後続する計算を扱うことが出来るモナド。継続に関しての詳しい説明は以下の文献を参考にしてください。
実はwithBreak $ \break -> ...のbreakは後続する計算をただ捨てているだけなのだ。
ここではwithBreakをさらに分解して何が起きているのかを理解することにする。まずContTは
newtype ContT r m a = ContT { runContT :: (a -> m r) -> m r }
この様に定義されていて、要するに(a -> m r) -> m rだ。callCCの実装は
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は
withBreak :: ((a -> (b -> m r) -> m r) -> (a -> m r) -> m r) -> m r
withBreak f = f (\x _ -> pure x) pure
となる。最初のプログラム中でfに対応するものは\break -> ...の部分である。ここで初めてbreakは
break :: a -> (b -> m r) -> m r
break = \x _ -> pure x
のようなものであることがわかった。
もう一度継続モナドに戻る。ContTのモナドの実装は
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に合わせて書き直すと
(>>=) :: ((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の挙動を見るために以下のような式を考える。
actionA >> break () >> actionB
まず左側の>>を展開する
(\c -> actionA (\_ -> break () c)) >> actionB
次にbreakを展開してみる
(\c -> actionA (\_ -> pure ()) >> actionB
この時点で後続する計算cが消えていることがわかる。
最後に残った>>を展開する
\c -> actionA (\_ -> pure ())
actionBは綺麗に消えてしまった。
最初のプログラムに戻ろう。
withBreak $ \break ->
forM_ [1..] $ \i -> do
liftIO . putStrLn $ "Loop: " ++ show i
when (i == 5) $ break ()
すでに見たようにiが5に達してbreakが評価された時点で後に続く無限の計算は捨てられていたのである