継続渡しなHaskellライフ

CPS(Continuation passing style, 継続渡しスタイル)は、関数型プログラミングにおけるプログラムの書き方の一つである。CPSを導入する簡単な例をいくつか紹介しよう。

まず、入力された数値が3の倍数かどうかを判定するプログラムを作ってみよう。

foo :: IO Bool
foo = do
   n <- readLn :: IO Int
   return (n `mod` 3 == 0)

ここで「CPS変換」なる儀式を行うと…こうなる！

foo' :: (Bool -> IO r) -> IO r
foo' cont = do
   n <- readLn :: IO Int
   cont (n `mod` 3 == 0)

「なにこれ、returnを置き換えただけじゃねえか！意味わかんねー！」という声が聞こえてきそうだが、もう少し考えてみよう。

3の倍数が入力されたらFizz、5の倍数が入力されたらBuzz、15の倍数はFizzBuzz、それ以外は元の数を返すようなプログラムは、普通に考えればこのようになる。

bar :: IO (Either Int String)
bar = do
    n <- readLn :: IO Int
    case (n `mod` 3, n `mod` 5) of
        (0, 0) -> return $ Right "FizzBuzz"
        (0, _) -> return $ Right "Fizz"
        (_, 0) -> return $ Right "Buzz"
        _ -> return $ Left n

barの結果はパターンマッチによって分岐することができるが、あることに気づくかもしれない。そう、条件分岐の結果を一旦代数的データ型に押し込み、それに対してさらに条件分岐を行おうとしているのだ……

さて、barをCPS変換するとこうなる。

bar' :: (Int -> IO r) -> (String -> IO r) -> IO r
bar' left right = do
    n <- readLn :: IO Int
    case (n `mod` 3, n `mod` 5) of
        (0, 0) -> right "FizzBuzz"
        (0, _) -> right "Fizz"
        (_, 0) -> right "Buzz"
        _ -> left n

bar'の結果について分岐するには、Intが返ってきた場合の処理、Stringが返ってきた場合の処理をそれぞれ直接渡せばいいので、パターンマッチは不要だ。

打って変わって、今度はfooを4で割った商も一緒に返すように変更してみよう。

baz :: IO (Bool, Int)
baz = do
   n <- readLn :: IO Int
   return (n `mod` 3 == 0, n `div` 4)

bazの結果であるタプルをBoolとIntに分解するには、やはりパターンマッチしなければいけない。そこでbazをCPS変換するとこのようになる。

baz' :: (Bool -> Int -> IO r) -> IO r
baz' cont = do
   n <- readLn :: IO Int
   cont (n `mod` 3 == 0) (n `div` 4)

こちらは関数にBoolの値とIntの値が別々に渡されるので、タプルもパターンマッチも使う必要はない。

つまり、継続渡しスタイルを使うと計算の結果を代数的データ型を介さずに受け渡しできるのだ！そのメリットは明らかである。

CPSはattoparsecなどの様々なライブラリで利用されている。Haskellのプログラムを高速化したいならば、ぜひCPS変換することを検討してみてほしい。