bigsleepの日記

 | 

2012-09-19

継続モナドメモ

22:18

あんまり使わないらしいんですが、興味があったので調べていました。

なんだか難しいので理解するためのメモです。

定義

The Continuation monad

によると

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) } -- r は計算全体の最終の型
  
instance Monad (Cont r) where 
    return a       = Cont $ \k -> k a                       -- i.e. return a = \k -> k a 
    (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k) -- i.e. c >>= f = \k -> c (\a -> f a k) 

((a -> r) -> r)というのは限定継続のshiftの型に似てます。

これが多分継続を関数として受け取ってなにか値を返す、継続を制御する関数のようです。

returnは何か値を受け取ってそれを継続に適用して結果を返す関数を作ります。

>>=の方は難しそうです。

使ってみる

import Control.Monad.Cont

ex1 :: Cont Int Int
ex1 = do a <- return 1
         b <- return 10
         return $ a + b

main = print $ show $ runCont ex1 \x -> x

この結果は11でした。後traceで表示させたら、aには1、bには10が入ってました。


import Control.Monad.Cont

ex2 :: Cont Int Int
ex2 = do a <- return 1
         b <- return 10
         c <- cont $ \k1 -> -1 --継続を使ってない
         d <- cont $ \k2 -> -2
         return $ a + b + c + d

main = print $ show $ runCont ex2 \x -> x

この結果は-1でした。cの行で継続を捨てて関係ない値を返してます。



import Control.Monad.Cont

ex3 :: Cont Int Int
ex3 = do a <- return 1
         b <- return 10
         c <- cont $ \k1 -> k1 $ a + b
         d <- cont $ \k2 -> k2 $ a + b + c
         return $ a + b + c + d

main = print $ show $ runCont ex2 \x -> x

どうもdo文の中で<-で束縛される値は継続に渡される値になるようです。

returnだとreturnの引数で、この例のcにはa+b、dにはa+b+cが入るようです。

それでa = 1, b = 10, c = 11, d = 22, 最後の結果は44になりました。

継続を捨てる場合にはモナド値にはなにも入らないということになるんだろうか。


>>=

newtype Cont r a = Cont { runCont :: ((a -> r) -> r) } -- r は計算全体の最終の型
  
instance Monad (Cont r) where 
    return a       = Cont $ \k -> k a                       -- i.e. return a = \k -> k a 
    (Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k) -- i.e. c >>= f = \k -> c (\a -> f a k) 

>>=の定義を見てみます。

現在の継続を受け取り、新しく継続を作って前の継続制御に渡して結果を取得するという、継続制御を作る。

新しい継続は、後ろの継続制御に現在の継続を適用して結果を得る関数

継続の名前の通り、以降の処理が継続のなかに、含まれるようになってる。

モナド値は後ろの継続制御の中で使われたりする。

Contモナドをつないだものは、resetの中にshiftが複数ある場合とだいたい似たような感じかも。

Generatorみたいなのを書いてみる

前にscalaでreset/shiftを使って書いたGeneratorと似たようなことをしてみます。

なんかまだまだHaskellに慣れてなくてこれだけ書くのにめちゃくちゃ時間かかってます。

遅延評価されるならただListを作って上から使っていくだけでもいいのかもしれません。

無限Listとかもあるらしいし。

import Control.Monad.Cont

data Result r = Done | Next (r, () -> Result r)

generate :: r -> Cont (Result r) ()
generate x = cont $ \k -> Next (x, k)

done = cont $ \k -> Done

code :: Cont (Result Int) ()
code = do generate 1
          generate 2
          generate 3
          generate 4
          generate 5
          do generate 6
             generate 7
          hoge

hoge :: Cont (Result Int) ()
hoge = do generate 8
          generate 9
          generate 10

gen :: Result Int
gen = runCont code $ \_ -> Done

test :: Result Int -> IO ()
test x = case x of
              Done -> print "done"
              Next (a, k) -> do {print a; test $ k ();}

main = test gen

木の走査

木がある要素を含んでいるかどうか、前順走査して探す。

import Control.Monad.Cont

data Result r = Done | Next (r, () -> Result r)
generate :: r -> Cont (Result r) ()
generate x = cont $ \k -> Next (x, k)

data Tree a = Leaf | Node a (Tree a) (Tree a) deriving (Show)

mytree :: Tree Char
mytree = (Node 'A' (Node 'B' (Node 'C' Leaf (Node 'D' Leaf Leaf)) Leaf) Leaf)

walkTree :: Tree a -> Cont (Result a) ()
walkTree (Node a l r) = do generate a
                           walkTree l
                           walkTree r
walkTree Leaf = return ()

find :: (Eq a) => Tree a -> a -> Bool
find t a = findG g a
    where g = runCont (walkTree t) $ \_ -> Done

findG :: (Eq r) => Result r -> r -> Bool
findG (Next (a, k)) b = if (a == b) then True
                                    else findG (k ()) b
findG Done _ = False

main = if find mytree 'C'
           then print "mytree contains C"
           else print "mytree does not contain C"
 |