2009年11月12日木曜日

Haskell の State モナド (2) - 「状態を変更する関数」を `つなげる関数' を共通部品として括り出す

Haskell の State モナド (1) - 状態を模倣する の続き。

… しかし、前回の内容忘れてもうた。。

パタッ(o_ _)o~†

 

復習

前回は、スタックの内容を変更する pop, push などを連続して適用するために、状態を変更する関数と関数を つなげる comb 関数を定義した。(Control.Monad.State は使わずに。)

ポイントは、最初に、

関数と関数を「つなげる関数」を意識する。

090923-002

そのためには、

関数を「適用する値」と、「適用する関数」に分割して考える

例えば、次のような apply 関数を定義したら、

apply a f = f a

直接、関数 (演算子) に適用する方法と、意識的に分割して適用する方法があることを認識しておく。

*Main> 100 + 1
101
*Main> apply 100 (+ 1)
101

091011-003

手段としては、

    1. 無名関数クロージャで 内側へ内側へ…と計算をつなげ、
    2. 一番内側の関数で自由変数の値を使って計算を組立てる

例えば、3 つの引数を足し合わせる関数 add3 の定義は、

add3 x y z = x + y + z

これを次のように無名関数とクロージャで書くことができる。

add3 = \x -> \y -> \z -> x + y + z

無名関数とクロージャで書かれていたら、省略されている括弧を頭の中で補完。束縛関係を明確に意識する。

add3 = \x -> (\y -> (\z -> x + y + z))

091112-008.png

先ほどの apply 関数と、無名関数・クロージャを使えば、100 + 200 + 300 を次のように書くことができる。

*Main> 100 `apply` (\x -> 200 `apply` (\y -> 300 `apply` (\z -> x + y + z)))
600

これが関数を「つなげる」ことの原型となる。

後は … 端折って、「型に注意しましょう」ということで。 ^^;

 


B0012ORJAM

カウンタの例

前回と同じように、今回は「数を数えるための カウンタ」を操作する関数を「つなげる」ことを考える。

最初に、カウンタの「値」と「増分」をフィールドに持つ Counter a 型を定義。

data Counter a = Counter { val       -- 値
                         , step :: a -- 増分
                         } deriving Show

 

状態を変更する関数

次に、カウンタの値を増分だけ増やす next 関数を定義する。このとき、後で関数をつなげることができるように、前回のスタックの pop 関数のように

pop :: Stack a –> (b, Stack a)

の形に沿った関数の型にする。

next :: Num a => Counter a -> (a, Counter a)
next (Counter v s) = let v' = v + s
                     in (v', Counter v' s)

ここでは返されるタプルの第1要素は、next が適用された後のカウンタの「値」としておいた。

例えば、値 0、増分 1 のカウンタに対して next 関数を適用すると、

*Counter> next (Counter 0 1)
(1,Counter {val = 1, step = 1})

 

「状態を変更する関数」に別名を付ける

前回と同じように next 関数を つなげる 関数を考える。まずは、関数の型が長いと読みにくいので、カウンタを操作する関数の型を「カウンタ操作型」として別名を付ける。

type CounterOp a b = Counter a -> (b, Counter a)

ここで注意することは 型変数 a, b 。上記の next 関数では、たまたまタプルの第1要素がカウンタの値と同じ型だった。しかし、カウンタを操作する関数を他に定義した場合、別の型にしたいこともあるかもしれない。カウンタで使われる値の型の方は、当然ながらカウンタ操作する前と後では変わらない。

 

「状態を変更する関数」を つなぐ 関数

次に上記のカウンタ操作型を つなげる 関数を定義。なぜこのように定義するかは前回を参照。今回は一気に端折って、

comb :: CounterOp a b -> (b -> CounterOp a c ) -> CounterOp a c
comb m n = \counter0 -> let (val1, counter1) = m counter0
                            (val2, counter2) = n val1 counter1
                        in  (val2, counter2)

comb 関数の第2引数が、第1引数に対して全く関心がない場合のために comb_ 関数を定義しておく。

comb_ :: CounterOp a b -> CounterOp a c -> CounterOp a c
comb_ m n = m `comb` \_ -> n

 

ここでカウンタを連続して 3 回カウントさせる next3 関数を上記の comb_ 関数を使って定義してみる。

next3 = next `comb_` next `comb_` next

これを先ほどと同じカウンタに適用すると、

*Counter> next3 $ Counter 0 1
(3,Counter {val = 3, step = 1})

 

ついでなので、next を 3 回つなげて、カウンタの値を足し合わせる関数を定義してみる。

… と、その前に前回と同じように、ある値に適用すると CounterOp a b 型の値を返す関数 ret を定義しておく。ただし、ret 関数では counter の更新は行わない。単に b 型の値を CounterOp a で包むだけ。

ret :: b -> CounterOp a b
ret x = \counter -> (x, counter)

これを元に、

next3' = next `comb` \x1 ->
         next `comb` \x2 ->
         next `comb` \x3 ->
         ret $ x1+x2+x3

早速使ってみる。

*Counter> next3' $ Counter 0 2
(12,Counter {val = 6, step = 2})

 

ここまでのコード

 

スタック操作型 と カウンタ操作型 の比較

ところで、前回のスタックを操作するときに定義 した「スタック操作型」は、次の通りだった。

type StackOp a b = Stack a -> (b, Stack a)

これに対して、今回の「カウンタ操作型」は、

type CounterOp a b = Counter a -> (b, Counter a)

違いは「別名」と、そこで「状態を変更する対象」である具体的な型コンストラクタ

 

comb 関数も同様に見てみると、「スタック操作」版は、

comb :: StackOp a b -> (b -> StackOp a c) -> StackOp a c
comb m n = \stack0 ->
           let (x1, stack1) = m stack0
               (x2, stack2) = n x1 stack1
           in  (x2, stack2)

「カウンタ操作」の comb 関数は、

comb :: CounterOp a b -> (b -> CounterOp a c ) -> CounterOp a c
comb m n = \counter0 -> let (val1, counter1) = m counter0
                            (val2, counter2) = n val1 counter1
                        in  (val2, counter2)

 

ret 関数も同じく「スタック操作」版は、

ret :: b -> StackOp a b
ret x = \stack -> (x, stack)

「カウンタ操作」版は、

ret :: b -> CounterOp a b
ret x = \counter -> (x, counter)

 

「もう、これは共通部分をまとめるしかない」という雰囲気になった。 ^^;

 

State s a 型 (状態 操作型) にまとめる

最初に別名から考える。「スタック操作型」と「カウンタ操作型」を総称する名前にしたいので、「状態操作型」という意味で State s a 型という名前にした。(もちろん、Control.Monad.State.LazyState を真似て…)

type State s a = s -> (a, s)

先ほど具体的な型が書かれていた StackOp, CounterOp の部分を型変数 s とした。 いきなりこの定義を見たら、抽象的な関数で具体的なイメージがわかない。しかし、これに対応した具体的な関数を連想できるので、State s a 型は 状態を変更する関数を表現したものだと解釈できる。

 

これに伴い、同じように comb 関数も具体的な型名を型変数で置き換える。

comb :: State s a -> (a -> State s b) -> State s b
comb m n = \s0 -> let (x1, s1) = m s0
                      (x2, s2) = n x1 s1
                  in  (x2, s2)

ret 関数も同じく、

ret :: a -> State s a
ret x = \s -> (x, s)

 

ここまでのコード

… しかし、これだけ見たら、本当わからんなぁ。。 (+_+)

とにかく、これで スタックを操作していたモジュールと、Counter モジュールに記述していた comb, comb_, ret 関数を削除し、上記の State をインポートすればよくなった。

counter.hs

stack.hs

main.hs

main.hs の main を実行した結果は、

*Main> main
(3,Counter {val = 3, step = 1})
((),Stack [300,200,100,5,4,3,2,1])