状態モナドの練習(1)

状態モナドを理解するために、記号表を更新するシナリオを考えた。

環境

文字と整数のタプルからなる、単純な連想リスト構造を考える。

type Name = String
type Value = Int
type Env = [(Name, Value)]

この連想リストを変数名とその変数の値からなる環境（記号表）とみなすことにする。環境に対する操作は、変数名と値の登録、値の更新、変数名に対する値の取得、変数名の削除がある。純粋関数型言語であるHaskellでは、連想リストを直接更新することはできない。そこで、1)2)3)4)に習い、段階的にリファクタリングし、最終的に状態モナドを導入する。

環境に対する操作

値の更新手段が無いHaskellでは、変数名と値を登録したり値を更新する際、連想リストを直接更新することはできない。その代わり、新しい環境を返す。変数名に対する値の取得操作では、記号表は変わらず値を返す。
この create, read, update, delete, を統一的に扱い、常に値と環境のタプルを返すことにする。

Env -> (Value, Env)

具体的な関数は以下の通り（ここでは更新と新規の登録を一つの関数にまとめた）。

delVar :: Name -> Env -> ((), Env)
delVar k [] = ((), [])
delVar k ((k1,v1):ks) = if k1 == k then
                            ((), ks)
                        else
                            ((), (k1, v1) : e')
                                where
                                  (_, e') = delVar k is

setVar :: Name -> Value -> Env -> (Value, Env)
setVar k v e = case lookup k e of
                  Just x -> (v, (k, v) : e')
                      where
                        (_, e') = delVar k e
                  Nothing -> (v, (k, v) : e)

getVar :: Name -> Env -> (Value, Env)
getVar k e = case lookup k e of
                Just x -> (x, e)
                Nothing -> error "invalid key"

環境に対する処理を連続して行う例を考えると、タプルを返す意味が明らかになる。簡単な例として、変数の値を破壊的に+1する操作を考える(Common Lisp の incf に相当)。

incf0 k e =
    let
        (v1, e1) = getVar k e
        (v2, e2) = setVar k (v1 + 1) e1
    in
      (v2, e2)

この例では、一度環境から値を取得して変数に束縛した後、１を足し、環境を更新している。実行すると以下のようになる。

*Main> incf0 "x" [("x",3)]
(4,[("x",4)])

計算のつなぎ合わせ

incf0 は単純だったが、より複雑な処理を考えることもできる。（処理自体に意味はないが）以下のようにincf0も部品として用い、連続した処理を考えることもできる。

-- (let ((x 3) (y 4)) (incf x) (decf y) (incf x) x)
ex3 =
    let
        e = [("x", 3),("y", 4)]
        (v1, e1) = incf0 "x" e
        (v2, e2) = decf0 "y" e1
        (v3, e3) = incf0 "x" e2
        (v4, e4) = getVar "x" e3
    in
      (v4, e4)

ここで、e1,e2,e3,v1,v2,v3 の変数は、次の計算に渡されるだけで他には全く利用されていない。incf0 にも、ex3 にも、同じようなパターンがあることが見て取れる。そこで、計算と計算をつなぎ合わせる「糊」を考えて抽象化することを試みる。
計算をつなぎ合わせる際、直前の計算結果を次の計算が使う場合と、使わない場合がある。それぞれ、comb, comb_ と名付けると、以下のように書ける。

comb :: (Env -> (Value, Env)) -> (Value -> (Env -> (Value, Env))) -> (Env -> (Value, Env))
comb openv1 openv2 e = 
    let (v1, e1) = openv1 e
    in (openv2 v1 e1)

comb_ :: (Env -> (Value, Env)) -> (Env -> (Value, Env)) -> (Env -> (Value, Env))
comb_ op1 op2 = op1 `comb` \_ -> op2

この comb, comb_ を用いると先の冗長な計算を書き換えることができる。

incf k = getVar k `comb` (\v -> setVar k (v + 1))
decf k = getVar k `comb` (\v -> setVar k (v - 1))

ex3' =
    let
        e = [("x", 3),("y", 4)]
        (v4, e4) = (incf "x" `comb_` decf "y" `comb_` incf "x" `comb_` getVar "x") e
    in
      (v4, e4)

どちらも、糊で関数をつなぎあわせることで計算結果を保持する変数が不要となった。定義上、comb, または comb_ でつないだ処理は、Env -> (Value, Env) の型を持つ。そのため、同じ型の計算をいくらでもつなぎあわせることができる。

このような抽象化のパターンは、状態モナドを用いるとさらに簡潔に書くことができる。
（長くなったので続く）

参考資料