人気ブログランキング | 話題のタグを見る

Haskell/Continuation passing style 3

引き続き Haskell/Continuation passing style を解読する。

callCC

callCC とは "call with current continuation" の略だ。まず次の簡単な例から見ていく。

-- Without callCC
square :: Int -> Cont r Int
square n = return (n ^ 2)

-- With callCC
square :: Int -> Cont r Int
square n = callCC $ \k -> k (n ^ 2)

上が callCC を使わないで単に Cont モナドで記述した例だ。ghci で試すと次のようになる。

Prelude> import Control.Monad.Cont
Prelude Control.Monad.Cont> let square n = return (n^2)
Loading package transformers-0.3.0.0 ... linking ... done.
Prelude Control.Monad.Cont> runCont (square 2) print
4

2番めの例が callCC を使った例だ。callCC は引数に \k が引数で、k (n^2) が戻値の関数をとる。k には実行時に任意の継続(関数)を与える。ghci で実行すると次のようになる。

Prelude Control.Monad.Cont> let square2 n = callCC $ \k -> k (n^2)
Loading package mtl-2.1.1 ... linking ... done.
Prelude Control.Monad.Cont> runCont (square 2) print
4

上の2つの例は同じ動作をするが、callCC が引数に継続を明示しているところが異なる。2つのプログラムは同じように見えるが、callCC を使うと何時、どのような値で継続を使うのかをコントロールできる。その驚くべき効果を見てみよう。

Deciding when to use k

次のプログラムは継続を何時、どのように呼び出すかをコントロールできる、callCC の効用を示す例だ。

foo :: Int -> Cont r String
foo n =
  callCC $ \k -> do
  let n' = n ^ 2 + 3
  when (n' > 20) $ k "over twenty"
  return (show $ n' - 4)

ghci で実行すると次のようになる。

Prelude Control.Monad.Cont> :set +m
Prelude Control.Monad.Cont> let
Prelude Control.Monad.Cont| foo n =
Prelude Control.Monad.Cont|   callCC $ \k -> do
Prelude Control.Monad.Cont|     let n' = n ^ 2 + 3
Prelude Control.Monad.Cont|     when (n' > 20) $ k "over twenty"
Prelude Control.Monad.Cont|     return (show $ n' - 4)
Prelude Control.Monad.Cont|
Prelude Control.Monad.Cont> runCont (foo 2) print
"3"
Prelude Control.Monad.Cont> runCont (foo 5) print
"over twenty"

このプログラムは引数 n を2錠して3を足すが、その値が20を超えている場合、それ以降の処理を中断して継続 k に "over twenty" を引き渡している。(大域脱出を行なっている。)そうでない場合は、値から4を引いて return 関数を用いてそれを継続に引き渡す。これが手続き型の言語であれば k は return 命令と同じように見える。しかし、Haskell の場合 k は単に first-class の関数だから、when のような関数に渡したり Reader モナドの中で保存したりすることができる。

また、callCC は普通に do ブロックの中に埋め込むこともできる。

bar :: Char -> String -> Cont r Int
bar c s = do
  msg <- callCC $ \k -> do
    let s' = c : s
    when (s' == "hello") $ k "They say hello."
    let s'' = show s'
    return ("They appear to be saying " ++ s'')
    return (length msg)

ghci で実行すると次のようになる。

Prelude Control.Monad.Cont> let
Prelude Control.Monad.Cont| bar c s = do
Prelude Control.Monad.Cont| msg <- callCC $ \k -> do
Prelude Control.Monad.Cont| let s' = c : s
Prelude Control.Monad.Cont| when (s' == "hello") $ k "They say hello."
Prelude Control.Monad.Cont| let s'' = show s'
Prelude Control.Monad.Cont| return ("They appear to be saying " ++ s'')
Prelude Control.Monad.Cont| return (length msg)
Prelude Control.Monad.Cont|
Prelude Control.Monad.Cont> runCont (bar 'h' "ello") print
15

この例では k は goto 文のようにも見える。when の条件が一致すればその後の処理を行わず msg <- callCC .. の処理に移るからだ。次の例は、処理が k n のところで中断するので、return 25 はスキップされて実行されない。

bar :: Cont r Int
bar = callCC $ \k -> do
  let n = 5
  k n
  return 25

ghci で実行してみる。

Prelude Control.Monad.Cont> let
Prelude Control.Monad.Cont| baz = callCC $ \k -> do
Prelude Control.Monad.Cont|   let n = 5
Prelude Control.Monad.Cont|   k n
Prelude Control.Monad.Cont|   return 25 :: Cont r Int
Prelude Control.Monad.Cont|
Prelude Control.Monad.Cont> runCont baz print
5

(継続を利用すると、手続き型言語に見られる処理の中断や大域脱出を Haskell でも簡単に記述できるようだ。しかし、それらのロジックを頻繁に使うべきかどうかは別の問題だ。)

前へ 目次 次へ
by tnomura9 | 2013-07-13 17:09 | Haskell | Comments(0)
<< でんぱ組.inc. Haskell/Continu... >>