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

Haskell/Continuation passing style 2

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

Using the Cont monad

前回の記事で、継続渡しスタイルのプログラムはあるパターンをとっているのが分かる。プログラムを記述する上でこのようなメタ・パターンを知っておくことは大切だ。例えば pythagoras_cps では次のような記述があった。

square_cps x $ \x_squared ->

これは square_cps x の計算結果をラムダ記法の \x_squared 変数に束縛するという意味になるが、やや煩雑で、しかも、暗黙の決まり事がわかっていなければ読みにくい。Continuation モナドを使うとこのような煩雑な記述を隠蔽してスッキリと記述することができる。

次のプログラム cont_monad.hs は継続渡しスタイルのプログラム pythagoras_cps を Continuation モナドを使って記述した例だ。

import Control.Monad.Cont

add :: Int -> Int -> Int
add x y = x + y

square :: Int -> Int
square x = x * x

add_cont :: Int -> Int -> Cont r Int
add_cont x y = return (add x y)

square_cont :: Int -> Cont r Int
square_cont x = return (square x)

pythagoras_cont :: Int -> Int -> Cont r Int
pythagoras_cont x y = do
  x_squared <- square_cont x
  y_squared <- square_cont y
  sum_of_squares <- add_cont x_squared y_squared
  return sum_of_squares

実行例は次のようになる。do 記法で書かれたプログラムは Continuation モナドになるので、実行するためには runCont アクセサを使って Cont データ型のコンテナから関数を取り出す必要がある。

Prelude> :l cont_monad.hs
[1 of 1] Compiling Main ( cont_monad.hs, interpreted )
Ok, modules loaded: Main.
*Main> runCont (pythagoras_cont 3 4) print
25

次の newtype 宣言で分かるように、Cont データ型はフィールド名 runCont を持ち、そのフィールドの値は (a -> r) 型の関数を引数に取り、戻値として r 型のデータを返す。

newtype Cont r a = Cont { runCont :: (a -> r) -> r }

したがって、runCont (pythagoras_cont 3 4) は引数 print をとり、演算結果を print によってターミナルに表示し、戻値 IO () を返すことになる。

Cont モナド値 (Cont a r 型のデータ) の使い方がわかったので cont_monad.hs のコードを解読してみよう。

まず import Control.Monad.Cont で Cont モナドのモジュールをインポートする。次に、pythagoras_cont を記述するための部品である add_cont と square_cont を記述する。Cont モナドを利用してプログラムするためにこれらの関数は全て戻値が Cont モナド値になるようにプログラムする必要がある。

たとえば、add_cont 関数は Int 型の引数を2つとり、Cont r Int 型の値を返す。

add_cont :: Int -> Int -> Cont r Int
add_cont x y = return (add x y)

上のプログラムは return を使って (add x y) を Cont モナド型にラッピングしている。

pythagoras_cont もやはり Cont モナドの関数にするために do 記法で記述してある。do 記法で記述すると複数にネストしたラムダ記法を書かずに、手続き型言語風に継続渡しスタイルのプログラムを書くことができる。この pythagoras_cont 関数の戻値もまた Cont モナド型だ。

pythagoras_cont :: Int -> Int -> Cont r Int
pythagoras_cont x y = do
  x_squared <- square_cont x
  y_squared <- square_cont y
  sum_of_squares <- add_cont x_squared y_squared
  return sum_of_squares

モナドを使わない継続渡しスタイルの pythagoras_cps と Continuation モナドを使った pythagoras_cont とを比べてみると、後者のほうが随分読みやすくなっている。

Cont-value を戻値とする関数は暗黙に継続を引き渡している。return 関数は単に引数の値を継続に引き渡しているだけだ。また、>>= は次々に左項の継続を、右項の継続に引き渡していく。(このようにして Continuation モナドを利用すると、具体的な継続を隠蔽してプログラムを簡潔にすることができる。)

*Main> let square_C x = return (x ^ 2)
*Main> let addThree_C x = return (x + 3)
*Main> runCont (square_C 4 >>= addThree_C) print
19

(Cont r) のモナドインスタンスは次のようになる。

instance Monad (Cont r) where
  return n = Cont (\k -> k n)
  m >>= f = Cont (\k -> runCont m (\a -> runCont (f a) k))

return 関数は引数を単に継続に渡すだけだ。m >>= f は m の結果に f を関数適用させその結果を継続に引き渡して新しい継続を作成している。新しい継続はネストした関数になる。(この複雑にネストした継続は Cont モナドの中からは見えない。)

前へ 目次 次へ
by tnomura9 | 2013-07-08 19:52 | Haskell | Comments(0)
<< Haskell/Continu... Haskell/Continu... >>