継続モナド
型の定義
code:hs
newtype Cont r a = Cont {
runCont :: (a -> r) -> r
}
型引数の意味を理解する
例えば、普通に継続渡しでaddを書いてみる
code:hs
addCPS :: 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の計算結果」を適用した型
実装
code:hs
instance Monad (Cont r) where
return a = Cont $ \k -> k a
(Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k)
https://gyazo.com/7c06ed70ca2922751a0fc4bbe1d999af
上が継続モナドなし、下があり
黄色の部分にとって、緑の部分が継続になっている
↑の図には色を付けていないが内側も同様
継続の入れ子になっている
定義の意味
Haskellでは遅延評価があるため継続はあまり必要にならない ref そうなん？mrsekut.icon
嬉しさ
途中の？継続を扱いやすくなる
これはよくわかっていないmrsekut.icon
たぶん普通に継続の嬉しさの話なんだろうけど、それをそもそも知らない
pursでは、最初からContTで作られ、ContはそのIdentityで定義している
素直に実装すると以下のようになる
code: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を提供する
code:hs
class (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
応用例
大域脱出
直線作図機能