継続
文献を紐解くと、 継続とは「これから行われるであろう計算をパッケージ化したもの」とある。
出典: なんでも継続
継続は一般的な概念であるがここではHaskellの継続渡しスタイルとCont Monadについて説明する
継続渡しスタイル
- CPS というプログラミングスタイルの導入の話
- The Mother of all Monads
- Control.Monad.Cont
- Haskell/Continuation passing style
- Compiling With CPS
- Haskell で継続渡しスタイル (CPS)
- The mtl-c package
- Resource Management in Haskell
- データ型のCPS変換について
- Continuations all the way down
- Chris Dumas - Church-encoded datatypes in Haskell
- Chris Dumas - Church-encoded datatypes in Haskell, part 2
- A Gentle Run-through of Continuation Passing Style and Its Use Cases
- Defunctionalize the Continuation
- 並行プログラミングと継続モナド
-- Another junior Haskell programmer
fac 0 = 1
fac n = n * fac (n-1)
-- Continuation-passing Haskell programmer
facCps k 0 = k 1
facCps k n = facCps (k . (n *)) (n-1)
fac = facCps id
出典: The Evolution of a Haskell Programmer
Contモナド
newtype Cont r a = Cont { runCont :: (a -> r) -> r }
- 継続モナドについて - Qiita
- 継続モナドについて - Qiita
- 継続モナドによるリソース管理
- Continuation Passing Style in Haskell
- 無限ループから抜け出すプログラム
- Tweet
- ContT を使ってコードを綺麗にしよう！
- Forking and ContT (I)
- ContT, withLifted and resetContIO (II)
- Fun fact: The continuation monad
Cont r ahas an equality instance whenris finite. : haskell - Why would you use ContT?
- Lysxia - The reasonable effectiveness of the continuation monad
- How does the continuation monad work? | Max Hallinan
- Nested loops and continuations : Inside 245-5D
継続による計算の効率化
継続を使って短絡評価が実装できる
prod :: (Eq a, Num a) => [a] -> a
prod l = (`runCont` id) $ callCC (\k -> loop k l)
where
loop _ [] = return 1
loop k (0:_) = k 0
loop k (x:xs) = do
n <- loop k xs
return (n * xs)
shift/reset
- shift/reset プログラミング入門
- Introduction to Programming with Shift and Reset
- Shift to control
- shift/reset と control/prompt の違い
-- shift/reset for the Cont monad
shift :: ((a -> Cont s r) -> Cont r r) -> Cont r a
shift e = Cont $ \k -> e (return . k) `runCont` id
reset :: Cont a a -> Cont r a
reset e = return $ e `runCont` id
Symmetric Lambda Calculs
値（1 -> X）と継続(Y -> 0)は双対
Filinski, Andrzej. Declarative continuations and categorical duality. Univ., 1989.
米田埋め込み
The Yoneda embedding is familiar in category theory. The continuation passing transform is familiar in computer programming. They’re the same thing! Why doesn’t anyone ever say so?
出典: The Continuation Passing Transform and the Yoneda Embedding
CPSへの変換は米田埋め込みに対応している
cps :: forall a b r. (a -> b) -> ((b -> r) -> (a -> r))
cps = flip (.)
出典:CPS（継続渡し方式）変換をJavaScriptで説明してみるべ、ナーニ、たいしたことねーべよ
論理学での継続
CPS変換は、二重否定による古典論理の直観主義論理への埋め込みにあたる。