Haskellでの継続

継続とは、特定の瞬間におけるプログラムの状態であり、その状態を使用してその状態に戻ることができます。
継続の助けを借りて、例外処理、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プログラムの高速化と小型化