継続の助けを借りて、例外処理、gotoへの類似性、および命令構造を思い出させる他の多くのものを実装できます。
また、継続を使用して、不要な「ラップ」とパターンマッチングを削除することにより、プログラムのパフォーマンスを向上させることができます。
この記事では、Haskellで拡張機能を実装する方法と、それらと連携する興味深い機能をいくつか紹介します。
継続スタイルのプログラミング
はじめに、継続のスタイルでの継続とプログラミングとは何かを見てみましょう。
一般的な機能：
square :: Int -> Int
square x = x*x
incr :: Int -> Int
incr x = x+1
func :: Int -> Int
func x = square (incr x)
そして今、続編のスタイルで：
square_cps :: Int -> (Int -> r) -> r square_cps xk = k (x*x) incr_cps :: Int -> (Int -> r) -> r incr_cps xk = k (x+1) func_cps :: Int -> (Int -> r) -> r func_cps xk = incr_cps x $ \inc -> square_cps inc $ \sq -> k sq
これで、関数は引数自体に加えて、結果に適用される関数への入力を受け取ります。 これは続きです。
継続の助けを借りて、関数を接続できます。これは
func_cps
で
func_cps
ます。 最初に、
incr_cps
が
incr_cps
、その結果が継続
(\inc -> ...)
square_cps
(\inc -> ...)
に「落ち」、次に
square_cps
が
square_cps
その結果が継続
(\sq -> ...)
square_cps
(\inc -> ...)
に渡され、最後に最も外側の継続
k
に渡されます。
ここでの継続は、継続が
Int
を返す必要がないため、タイプ
(Int -> r)
です。
たとえば、結果をコンソールに出力するには、
print
を継続として渡すことができ
print
。
main = func_cps 5 print
モナド・コント
続編のスタイルでいくつかのパターンに気付くことができます。
たとえば、
square_cps
や
incr_cps
などの単純な関数は、同様の方法で宣言しました。
function ... = \k -> k (...)
そして、これらを次のように接続しました。
fun1 ... $ \r1 -> fun2 ... $ \r2 -> ...
これはすべてモナドを思い出させます。最初の例は
return
に似ており、2番目の例は
>>=
です。
モナドContを次のように紹介します。
newtype Cont ra = Cont { runCont :: (a -> r) -> r }
しかし、なぜ
(a -> r) -> r
？
実際、継続のスタイルで関数を記述した場合、各関数は計算を継続する追加のパラメーターを取りました。
引数で継続のスタイルで関数を「埋める」場合（継続まで）、その型は
(a -> r) -> r
になります。ここで
a
は関数の結果の型で、継続に渡さずに返した場合、
r
継続が返す結果のタイプ：
> :t square_cps 5
square_cps :: (Int -> r) -> r
Contをモナドにしてみましょう。
instance Monad (Cont r) where return n = Cont $ \k -> kn ...
return n
は、受信した継続にすぐにnを適用するContです。
m >>= f = Cont $ \k -> runCont m (\a -> runCont (fa) k)
m >>= f
は、Contです（
runCont
単にContを「アンパック」し、関数を解放します）
m
継続
(\a -> runCont (fa) k)
で、計算の結果である可能性があり、
a
（または関数は継続を無視できるため、取得できません）。 次に、
a
を
f
に適用して別のContを取得します。これは、
k
最も外側の継続で起動されます。
モナドContを使用してプログラムを書き換えます。
square_Cont :: Int -> Cont r Int
square_Cont x = return (x*x)
incr_Cont :: Int -> Cont r Int
incr_Cont x = return (x+1)
func_Cont :: Int -> Cont r Int func_Cont x = do inc <- incr_Cont x sq <- square_Cont inc return sq
main = runCont (func_Cont 5) print
今、すべてがはるかに明確に見えます。
Contで機能する関数に移りましょう。
callCC
簡単な例から始めましょう：
square :: Int -> Cont r Int
square n = callCC $ \k -> k (n*n)
役に立たない機能は何ですか？ Contコンストラクターの単なる同義語のようです。
しかし、それはそれほど単純ではありません。
callCC
のタイプを見てみましょう。
callCC :: ((a -> Cont rb) -> Cont ra) -> Cont ra
実際、
callCC
は（
callCC
(a -> Cont rb)
などの別の関数を取る関数を受け取り、
Cont ra
を返します。 つまり、この例の
k (n*n)
は
Cont r Int
型です。
callCC
何に使用できますか？ たとえば、関数をすばやく終了するには：
import Control.Monad (when) hehe :: Int -> Cont r String hehe n = callCC $ \exit -> do let fac = product [1..n] when (n > 7) $ exit "OVER 9000" return $ show fac main = do n <- fmap read getLine runCont (hehe n) putStrLn
私たちのプログラムを試してみましょう：
> main
3
6
> main
10
OVER 9000
このプログラムは階乗を計算し、9000を超えると判明した場合は「OVER 9000」というメッセージを返し、そうでない場合は単にその値を返します。
ここでは、命令型言語の戻り値として
exit
を使用しました。彼は計算を中断し、別の結果を導き出しました。
ネストされたcallCCブロックを使用することもできます。
bar :: String -> Cont r String bar s = do callCC $ \exit1 -> do let ws = words s names = foldl (\ac -> a ++ ", " ++ c) (head ws) (tail ws) r' <- callCC $ \exit2 -> do when (null ws) $ exit1 "No people" when (length ws == 1) $ exit2 "There is " return "There are: " return $ r' ++ names main = do ns <- getLine runCont (bar ns) putStrLn
試してみましょう：
> main
No people
> main
Bob
There is Bob
> main
Bob Alice
There are: Bob, Alice
名前のリストが空の場合、
exit1 "No people"
を呼び出し、内部ブロックを "ジャンプ"します。
人が1人だけの場合は「あり」を使用し、多くの場合は「あり：」を使用します。
計算がcallCCブロックでリターンに達すると、結果は通常どおり返されることに注意してください。
それでは、
callCC
関数はどのように
callCC
ますか？ 見てみましょう：
callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> ka)) k
通常の方法で始まり、Contで関数を継続のスタイルでラップします。 それから
(f (\a -> Cont $ \_ -> ka))
は
k
継続で始まります。
(\a -> Cont $ \_ -> ka)
は、何かを受け取ってContを返す関数で、その継続を無視して、代わりに
k
使用します。
仕組みを見てみましょう。
square n = callCC $ \k -> k (n*n)
= Cont $ \k' -> runCont ((\k -> k (n*n)) (\a -> Cont $ \_ -> k' a)) k'
= Cont $ \k' -> runCont ((\a -> Cont $ \_ -> k' a) (n*n)) k'
= Cont $ \k' -> runCont (Cont $ \_ -> k' (n*n)) k'
= Cont $ \k' -> (\_ -> k' (n*n)) k'
= Cont $ \k' -> k' (n*n)
すべてが期待どおりです。 より複雑なケースを考えてみましょう：
hehe :: Int -> Cont r String hehe n = callCC $ \exit -> do let fac = product [1..n] when (n > 7) $ exit "OVER 9000" return $ show fac = callCC $ \exit -> (when (n > 7) $ exit "OVER 9000") >> (return $ show (product [1..n])) -- let = Cont $ \k -> runCont ((\exit -> (when (n > 7) $ exit "OVER 9000") >> (return $ show (product [1..n]))) (\a -> Cont $ \_ -> ka)) k = Cont $ \k -> runCont ((when (n > 7) $ (\a -> Cont $ \_ -> ka) "OVER 9000") >> (return $ show (product [1..n]))) k = Cont $ \k -> runCont ((when (n > 7) $ (Cont $ \_ -> k "OVER 9000")) >> (return $ show (product [1..n]))) k
whenが機能すると、
(Cont $ \_ -> k "OVER 9000")
が返されます。 このContはその継続を使用しません。つまり、残りのコードは実行されません。
getCC
getCC
および
getCC'
関数を使用すると、現在の継続を「取得」し、それを使用してプログラムの前の状態に戻ることができます。
例：
foo :: Int -> Cont r String foo s = do (i, back) <- getCC' s when (i < 20) $ back (i*2) return $ show i
foo
、20以上になるまで引数を2倍にします。
> runCont (foo 5) id
"20"
> runCont (foo 3) id
"24"
> runCont (foo 2) id
"32"
(i, back) <- getCC' s
-
i
に
s
i
値を割り当て
i
この場所への「リンク」を作成します。
back (i*2)
-前の状態に戻りますが、
i
は
i*2
等しくなります。
これはすべてgotoによく似ていますが、ここでは過去の状態にしか移動できません。
getCC'
関数は次のように宣言されます。
getCC' :: t -> Cont r (t, t -> Cont ra) getCC' x0 = callCC (\c -> let fx = c (x, f) in return (x0, f))
それを理解してみましょう。 それを単純化し始めましょう：
getCC' x0 = Cont $ \k -> runCont ((\c -> let fx = c (x, f) in return (x0, f)) (\a -> Cont $ \_ -> ka)) k
= Cont $ \k -> runCont (let fx = (\a -> Cont $ \_ -> ka) (x, f) in return (x0, f)) k
= Cont $ \k -> runCont (let fx = Cont $ \_ -> k (x, f) in return (x0, f)) k
= Cont $ \k -> runCont (let fx = Cont $ \_ -> k (x, f) in Cont $ \k' -> k' (x0, f)) k
= Cont $ \k -> let fx = Cont $ \_ -> k (x, f) in k (x0, f)
f
関数は、引数とそれ自体のペアを外部（getCC'shnom）継続に適用し、Contでラップします。
そして
k (x0, f)
-引数
getCC'
と
f
ペアを外部継続に適用します。
他の場所で
f
を呼び出すと、現在の継続ではなく、
getCC'
現在の継続を使用してContを返します。 したがって、私たちは過去の状態に戻るようなものです。
また、
getCC'
には「弟」
getCC
がありますが、ContT（Contのトランスフォーマー）でのみ有用です：
import Control.Monad (when) import Control.Monad.Cont getCC :: MonadCont m => m (ma) getCC = callCC (\c -> let x = cx in return x) foo :: ContT () IO () foo = do back <- getCC liftIO $ putStr "Do you want to coninue? [y/n] " a <- liftIO $ getLine when (a == "y" || a == "Y") $ back main = runContT foo return
> main
Do you want to coninue? [y/n] y
Do you want to coninue? [y/n] y
Do you want to coninue? [y/n] n
>
プログラムは、ユーザーに「n」と答えるまで続行する許可を求めます。
これは、
getCC
が過去の状態に戻ることのみを許可し、引数を渡す機会を与えないことを示しています。
Contはどこで使用すればよいですか？
拡張機能の助けを借りて、プログラムの進行を柔軟に制御し、関数が完了する前に関数から戻り、例外システムを作成できます。
また、別のときに計算に戻ることにより、計算を「中断」することもできます（たとえば、Hugsは継続を使用して並行性を実装します）。
基本的に、Contはトランスフォーマーなどの他のモナドと組み合わせて使用されます。 これにより、複雑な制御構造の作成や計算の高速化が容易になります。
使用材料のリスト
継続受渡しスタイル
ハスケルの後藤
Haskellプログラムの高速化と小型化