Continuation Monad (1)
t-y-schemeの継続についての章であるChapter 13をHaskellで書いてみる。
まず13.1章。
13.1 call-with-current-continuation
Example 1
(+ 1 (call/cc (lambda (k) (+ 2 (k 3))))) => 4
Continuationモナドを利用する。(+)や整数リテラルがtype classのメソッド(?)であることを利用してliftMすることにする。
instance Show a => Show (Cont r a) where instance Eq a => Eq (Cont r a) where instance Num a => Num (Cont r a) where a + b = liftM2 (+) a b fromInteger = return . fromInteger
そうすると:
f00 :: Cont r Int f00 = 1 + callCC (\k -> 2 + k 3)
*Main> runCont f00 id 4
元のコードそっくりである*1。
Example 2
(define r #f) (+ 1 (call/cc (lambda (k) (set! r k) (+ 2 (k 3))))) => 4 (+ 3 (r 5)) => 6
今度は継続を保存しなくてはいけない。Stateモナドでやってみる。型が自己再帰するので、ラップするための型が必要になる。
newtype ContTState r a b = ContTState {
unContTState :: ContT r (State (a -> ContTState r a b)) b }本体はこうなる。
f03 :: ContT r (State (Int -> ContTState r Int Int)) Int
f03 = 1 + callCC (\k -> do put (ContTState . k); 2 + k 3)
f04 = flip evalState undefined $
do x <- runContT f03 return
r <- get
y <- runContT (3 + unContTState (r 5)) return
return (x, y)
instance Show a => Show (ContT r m a) where instance Eq a => Eq (ContT r m a) where instance (Monad m, Num a) => Num (ContT r m a) where a + b = liftM2 (+) a b fromInteger = return . fromInteger
*Main> f04 (4,6)
でもSTモナドなら余計な型がいらず、簡単。
f05 :: STRef s (Int -> ContT r (ST s) Int) -> ContT r (ST s) Int
f05 r = 1 + callCC (\k -> do lift (writeSTRef r k); 2 + k 3)
f06 = runST (do r <- newSTRef undefined
x <- runContT (f05 r) return
k <- readSTRef r
y <- runContT (3 + k 5) return
return (x, y))
*Main> f06 (4,6)
