継続モナド
型の定義
hsnewtype Cont r a = Cont {
runCont :: (a -> r) -> r
}型引数の意味を理解する
例えば、普通に継続渡しでaddを書いてみる
hsaddCPS :: Num a => a -> a -> (a -> r) -> r
addCPS x y k = k $ x + yこれと上の
(a -> r) -> r の対応を考えると、以下のようになっていることがわかる a は継続渡し以前の add 関数の計算結果の型 a -> r は、継続 k の型 r は、継続 k に「 add の計算結果」を適用した型実装
hsinstance Monad (Cont r) where
return a = Cont $ \k -> k a
(Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k)継続を使う前後の比較 ref
上が継続モナドなし、下があり
黄色の部分にとって、緑の部分が継続になっている
↑の図には色を付けていないが内側も同様
継続の入れ子になっている
定義の意味
>
Haskellでは遅延評価があるため継続はあまり必要にならない ref
そうなん？
嬉しさ
CPSを直接スタイルで書くことができる
結果的にコールバック地獄が消え、簡潔になる
途中の？継続を扱いやすくなる
これはよくわかっていない
たぶん普通に継続の嬉しさの話なんだろうけど、それをそもそも知らない
call/ccができる
pursでは、最初からContTで作られ、ContはそのIdentityで定義している
素直に実装すると以下のようになる
purs(hs)newtype Cont r a = Cont ((a -> r) -> r)
instance Functor (Cont r) where
map f (Cont m) = Cont (\k -> m (\a -> k $ f a))
instance Apply (Cont r) where
apply (Cont f) (Cont v) = Cont (\k -> f (\g -> v (\a -> k (g a))))
instance Applicative (Cont r) where
pure a = Cont (\k -> k a)
instance Bind (Cont r) where
bind (Cont m) k = Cont (\k' -> m (\a -> case k a of Cont m' -> m' k'))
instance Monad (Cont r)
class Monad m <= MonadCont m where
callCC :: forall a. ((forall b. a -> m b) -> m a) -> m a
instance MonadCont (Cont r) where
callCC f = Cont (\k -> case f (\a -> Cont (\_ -> k a)) of Cont f' -> f' k)二重否定モナド
callCCを提供する
hsclass (Monad m) => MonadCont m where
callCC :: ((a -> m b) -> m a) -> m a
instance MonadCont (Cont r) where
callCC f = Cont $ \k -> runCont (f (\a -> Cont $ \_ -> k a)) k応用例
大域脱出
直線作図機能