1. 継続モナドに相当する関数を考える
前回は、「継続渡しスタイル」の関数の例を見た。
今回は、継続モナドにおける
(>>=) 関数
の定義について、順を追って考える。
All About Monads の Continuation モナド には、継続モナドが、以下のように定義されている。
newtype Cont r a = Cont { runCont :: ((a -> r) -> r) }
instance Monad (Cont r) where
return a = Cont $ \k -> k a
(Cont c) >>= f = Cont $ \k -> c (\a -> runCont (f a) k)
- 継続渡しスタイルの計算をフィールドに持つ型を定義し、
- その型コンストラクタを Monad クラスのインスタンスとしてる。
ここでは、Monad クラスについては立ち入らず、継続渡しスタイルの計算を「つなげる」関数を定義してみる。
2. 継続渡しスタイルでは、本質的な計算結果を、別の関数に引き渡す
継続渡しスタイルでは、関数の結果を返すのではなく、結果を別の関数に引き渡す。
継続渡しスタイル - Wikipedia によると、
継続渡しスタイルで書かれた関数は、通常の直接スタイル(direct style)のように値を「返す」かわりに、「継続」を引数として陽に受け取り、その継続に計算結果を渡す。継続とは、関数の計算結果を受け取るための（一般には元の関数とは別の）関数のことである。
継続渡しスタイルの関数を、次の2つの部分に分けて考えることができる。
- 本質的な計算
- 「本質的な計算」の結果を、別の関数に与える計算
ここで「本質的な計算」とは、継続以外の引数を元に、直接スタイルで定義する計算に相当するものと捉えておく。
継続渡しスタイルの例
直接スタイルの関数から、継続渡しスタイルの関数を定義してみる。
例えば、２つの値を足し合わせる関数 add の定義は、
add x y = x + y
add 関数を、継続渡しスタイルにする。
add_cps x y k = k $ x + y
add_cps が行う「本質的な計算」は、２つの値を足し上げること。
x + y
継続渡しスタイルでは、２つの値を足し上げた結果を、別の関数に与える。
k $ x + y
変数 k は「本質的な計算」の結果を受け取る 1 引数関数で、継続を表す。
3. 継続渡しスタイルおける「中間結果」と「最終結果」
add_cps 関数の型を調べると、
*Main> :t add_cps add_cps :: (Num a) => a -> a -> (a -> b) -> b
add_cps 関数に、足し上げる 2 つの数値を与えたときの型は、
*Main> :t add_cps 1 2 add_cps 1 2 :: (Num t) => (t -> b) -> b
add_cps 1 2 の計算結果は、
-
数値を受け取る1引数関数（継続）を与えると、
-
最終的な結果を生成する関数が返される。
一般的に、ある計算結果を受け取る1引数関数を与えると、最終的な結果を生成する関数の型は、
(a -> r) -> r
この関数における、型変数の意味を確認しておく。
-
型変数 a は、継続渡しスタイルにおける「本質的な計算」結果。
-
関数 (a -> r) は、「本質的な計算」の結果を与えると、最終的な結果を生成する 1 引数関数（継続）。
-
型変数 r は、継続を与えたときの最終結果。
ここまで、型変数 a に対して、「本質的な計算結果」という表現を使ってきた。理由は、継続渡しスタイルにおいて、「本質的な計算結果」を渡す先である継続は任意であり、関数が行う中心的な計算は、継続に渡す前の値であるため。
ただし、関数全体から見ると、
(a -> r) -> r
という型における型変数 a は、「最終的な計算結果」である型 r に対して、
「中間結果」
と見なせる。よって、以降、この型変数に対応する値を「本質的な計算」結果ではなく、「中間結果」と呼ぶ。
最初に、『継続渡しスタイルの計算を「つなげる」関数』を定義すると述べた。正確には、
-
継続渡しスタイルの計算に対して、「中間結果」を生成する引数が与えられており、
-
後は、継続を与えるだけの状態にある計算を「つなげる」関数。
4. 計算をつなげる方法
具体的な例で、継続渡しスタイルの関数を「つなげる」ことを考える。
先ほど、足し算の継続渡しスタイルを書いた。これに加え、かけ算と引き算の継続渡しスタイルを定義する。
mul_cps x y k = k $ x * y sub_cps x y k = k $ x - y
上記の関数から、
(a -> r) -> r
という型になる計算の例を挙げると、
- add_cps 1 2
-
mul_cps 3 3
-
sub_cps 9 4
これらの計算は、継続を与えると、最終的な結果が生成される。このような計算をつなげたい。
ここで、２つの継続渡しスタイルの計算 m, n を、「つなげる」方法について、次のように考える。
(1) により、計算 n は、計算 m の計算結果を参照できる。計算 n の型は、
a -> (a -> r) -> r
上記の計算例に当てはめると、以下のような関数となる。
-
\x -> mul_cps x 2
-
\x -> sub_cps x 3
-
\x -> sub_cps x 4
継続渡しスタイルでは、中間結果を、別の関数に渡す。
継続渡しスタイルにする前の、直接スタイルの関数で考えると、上例の計算を「つなげる」ことは、足し算、かけ算、引き算を組み合わせて計算を構成することを意味する。
大雑把なイメージで考えると、下図の通り。
-
計算を行い、
-
その結果を次の計算に渡し、
-
それを繰り返し、次々と連鎖させる。
(2) のように、計算をつなげた結果、つなげる前と同じ型の計算にする理由は、個別につないだ計算を、更に大きな計算の組み合わせの部品として使うことができるようにするため。
5. 継続渡しスタイルの計算をつなげる関数の実装
a. comb 関数の型
継続渡しスタイルの2つの計算をつなげる関数を comb とする。
comb 関数の第1引数は、継続渡しスタイルの関数において、後は、継続を与えるだけの状態である関数の型と捉えておく。
(a -> r) -> r
第2引数は、継続渡しスタイルの関数に対して、「中間結果」を受けとる引数を追加する。
a -> (a -> r) -> r
とりあえず、comb 関数の型を、以下のように考えておく。
comb :: ((a -> r) -> r) ->
(a -> (a -> r) -> r) ->
(a -> r) -> r
予め、comb 関数を使い、2 つの計算をつなげる方法を想像すると、
add_cps 1 2 `comb` \x -> mul_cps x 3
b. comb 関数の実装方針
上記の具体的な計算を見ながら、comb 関数を定義するとき、以下の2点を満たすことを考える。
-
comb 関数の第2引数に与える無名関数の引数 x は、add_cps の「中間結果」を与える。
-
comb 関数を適用した結果、add_cps 1 2 や mul_cps x 3 と同じ型になる。
c. comb 関数の実装
では、comb 関数の定義を順に考えていく。
comb 関数は、2つ計算をつなげる関数。よって、引数を２つ与える。
comb m n = …
引数 m の型は、(a -> r) -> r) 、引数 n の型は、(a -> (a -> r) -> r) 。
第1引数 m は継続渡しスタイルの関数で、継続が与えられると最終結果を生成する。そのため、計算 m の中間結果を、1引数関数（継続）に与える。よって、次のような無名関数を与える。
comb m n = m (\x -> … )
第2引数 n は、第1引数の中間結果を受けとる。よって、n に無名関数の引数 x を与える。これにより、comb 関数の第2引数に与える関数は、第1引数の計算の中間結果を参照できる。
comb m n = m (\x -> n x … )
この結果、関数 n から、継続渡しスタイルの関数が取り出される。
ところで、comb 関数により、2つの継続渡しスタイルの関数をつなげた結果、再び継続渡しスタイルとなるようにしたい。そのためには、1引数関数を与えると、最終的な結果が得られる関数となるようにする必要がある。
comb m n = \k -> m (\x -> n x … )
ここで、無名関数の引数 k は、1引数関数（継続）で、2つの継続渡しスタイルの計算をつなげた計算の「中間結果」を受け取る。つまり、k は comb 関数で構築した本質的な計算の結果を、最終的に渡す先の関数となる。
先ほど、第2引数である関数 n を、無名関数の引数 x に適用し、継続渡しスタイルの関数を取り出した。この関数の結果を受け渡す先として、関数 k を定義する。
comb m n = \k -> m (\x -> n x k)
d. comb 関数を使う
定義した comb 関数を使ってみる。
main = print $ (add_cps 1 2 `comb` \x ->
mul_cps x 3) id --> 9
3 つの計算をつなげてみる。
main = print $ (add_cps 1 2 `comb` \x ->
mul_cps x 3 `comb` \y ->
sub_cps y 4) id --> 5
e. comb 関数の型宣言を変更
上記2つの計算例は、中間結果と、最終的な結果が伴に数値だった。これを変更し、最後に文字列を返すようにしてみる。
main = print $ (add_cps 1 2 `comb` \x ->
mul_cps x 3 `comb` \y ->
(\k -> k $ "Answer: " ++ show y)) id
その結果、実行するとエラーがでた。(+_+) エラーが出ないようにするためには、comb 関数の型宣言を変える必要がある。
先ほど、comb 関数の型を、以下のように宣言した。この型では、第1引数の中間結果と、それを元に作る中間結果の型が同じ型であるという制約が付いてしまう。
comb :: ((a -> r) -> r) ->
(a -> (a -> r) -> r) ->
(a -> r) -> r
第1引数の中間結果から、他の型へ変換できるようにするためには、次のような型宣言にする。
comb :: ((a -> r) -> r) ->
(a -> (b -> r) -> r) ->
(b -> r) -> r
これにより、先ほどのエラーがでなくなる。
f. type 宣言
しかし、このままでは型宣言が長くて読みにくい。(@_@;
type 宣言で別名を付ける方が良い。
type Cont r a = (a -> r) -> r
上記の型を用い、comb 関数の型宣言を変更する。
comb :: Cont r a -> (a -> Cont r b) -> Cont r b先ほどエラーとなった comb 関数は、以下のように宣言していた。
comb :: Cont r a -> (a -> Cont r a) -> Cont r a
関数の型が長いときは、別名を付けた方が理解しやすい。
g. 中間結果を変換しない関数
継続渡しスタイルの計算を comb 関数でつなげる中で、与えられた中間結果の値を別の値に変換した。
例えば、以下の計算は、中間結果を与えると、別の値に変換する継続渡しスタイルの関数が返る。
-
\x -> mul_cps x 3
-
\y -> sub_cps y 4
これに対して、中間結果を与えても、値を変化させない継続渡しスタイルの関数を返す関数を定義したい。この関数を ret 関数とすると、型は、
ret :: a -> Cont r a
まずは、中間結果を、引数 x に与えると考える。
ret x = …
結果を継続渡しスタイルの関数で返すために、継続を受け取る1引数関数を返すとする。
ret x = \k -> …
中間結果を変換せずに、関数 k に引き渡せばよいので、以下のようになる。
ret x = \k -> k xret 関数を使った例を挙げる。
*Main> (add_cps 1 2 `comb` ret) id 3 *Main> (mul_cps 3 4 `comb` ret) id 12
comb 関数の第1引数の中間結果が、最終的に返されるのが分かる。
*Main> (ret 100 `comb` \x -> add_cps x 1) id 101
ret 関数により、任意の値を継続渡しスタイルの計算に投入し、comb 関数でつなげることができた。
よって、ret 関数を使うと、直接スタイルの関数の結果を、継続渡しスタイルにおける中間結果に変換できる。
*Main> :t ret $ 1 + 2 ret $ 1 + 2 :: (Num a) => (a -> r) -> r
そのため、先ほどの main 関数、
main = print $ (add_cps 1 2 `comb` \x ->
mul_cps x 3 `comb` \y ->
sub_cps y 4) id --> 5
を ret 関数を用いて、次のように書き換えることができる。
main = print $ (ret (1 + 2) `comb` \x ->
ret (x * 3) `comb` \y ->
ret (y - 4)) id
つまり、ret 関数と comb 関数を組み合わせることにより、普通に定義した関数を継続渡しスタイルの連鎖のなかに投入し、結果を別の関数に与え、計算を構築することが可能となる。
6. comb 関数を使う例
前回見た継続渡しスタイルの関数を、comb 関数使い、置き換えてみる。
各々、以下の定義を挙げる。
- 直接スタイル
- 継続渡しスタイル
- comb 関数を使う
階乗
fact n | n == 0 = 1
| otherwise = n * fact (n-1)
fact_cps n k | n == 0 = k 1
| otherwise = fact_cps (n-1) (\x -> k (n * x))
fact 0 = ret 1
fact n = fact (n-1) `comb` \x ->
ret $ x * n
累積
prod [] = 1 prod (x:xs) = x * prod xs
prod_cps [] k = k 1 prod_cps (x:xs) k = prod_cps xs (\y -> k (x * y))
prod [] = ret 1
prod (x:xs) = prod xs `comb` \y ->
ret $ x * y
木の葉の数を数える
leafCount (Leaf _) = 1 leafCount (Branch l r) = leafCount l + leafCount r
leafCount_cps (Leaf _) k = k 1
leafCount_cps (Branch l r) k = leafCount_cps l $ \x ->
leafCount_cps r $ \y ->
k $ x + y
leafCount (Leaf _) = ret 1
leafCount (Branch l r) = leafCount l `comb` \x ->
leafCount r `comb` \y ->
ret $ x + y
フィボナッチ数
fib n | n == 0 = 0
| n == 1 = 1
| otherwise = fib (n-1) + fib (n-2)
fib_cps n k | n <= 1 = k n
| otherwise = fib_cps (n-1) $ \x ->
fib_cps (n-2) $ \y ->
k $ x + y
fib n | n == 0 = ret 0
| n == 1 = ret 1
| otherwise = fib (n-1) `comb` \x ->
fib (n-2) `comb` \y ->
ret $ x + y
リストの平坦化
concat_ [] = ret [] concat_ (xs:xss) = concat_ xss `comb` \yss -> ret $ xs ++ yss
concat_cps [] k = k [] concat_cps (xs:xss) k = concat_cps xss $ \xss' -> k $ xs ++ xss'
concat_ [] = ret []
concat_ (xs:xss) = concat_ xss `comb` \yss ->
ret $ xs ++ yss
foldr
foldr_ _ z [] = z foldr_ f z (x:xs) = x `f` foldr_ f z xs
foldr2 _ z [] k = k z foldr2 f z (x:xs) k = foldr2 f z xs $ \y -> k $ f x y
foldr2 _ z [] = ret z
foldr2 f z (x:xs) = foldr2 f z xs `comb` \y ->
ret $ f x y
関連記事
- Haskell の State モナド (1) - 状態を模倣する
- Haskell の Writer モナド (1) – Control.Monad.Writer を使う前に
- Haskell の Maybe a 型と Either a b 型 (1) - 「結果を返しそこなう計算」、Java と比較しながら
0コメント:
コメントを投稿