Stateモナド

**”状態”を受け取り、状態に対する計算結果と、計算後の”状態”**を返す(状態付き計算とよぶ)ような関数を、モナドとして扱いたいときに用いるモナド
状態付き計算処理を簡潔に記述できる（関数合成できる）

参考

実装するまえに

状態付き計算とは

sを状態、sに対する何らかの計算結果をa、計算後の状態をs'としたとき、
以下の形で入出力が表現できる計算のこと。

s -> (a, s')

状態とは変数の値とかリストの中身とか、一般的な意味合いでの状態と思えばいい。

なぜ状態付き計算を使うのか

モナドが多く利用される純粋関数型プログラミング言語のHaskellのコードを例にとる。
以下は、スタック処理の例。

stackExample :: State [Int] Int
stackExample = do
  push 1
  push 2
  push 3
  pop
  push 4
  x <- pop
  return x
> runState stackExample []
> (4,[2,1])

(筆者はHaskellには触れたことがないので、コードそのものには特に言及しない。)
なにをやっているかに注目する。
上記プログラムは、1～4のデータを空の箱にに入れたり取り出したりし、最終的に 4 を取り出して 2 と 1 が残っている状態を表す、いわゆるスタック処理の一例である。
ここでは、変数への再代入なしに状態を更新しているようにふるまっている点が重要で、
このような処理を、Pythonで普通に実装しようとすると、例えば以下のように、
スタックの状態を保持するリストに対し、元々備わっている状態更新の処理を用いて、リストの中身を更新していく書き方になると思う。

def stackExample(state):
    state.insert(0,1)
    state.insert(0,2)
    state.insert(0,3)
    state.pop(0)
    state.insert(0,4)
    ret = (state.pop(0), state)
    return ret

stackExample([])

(4, [2, 1])

このままでも簡潔に記述できている。
しかしここで問題なのは、stateの変数がいまどのような状態なのか、どんな状態になりうるのかがわからないというところにある。
これを他の外部処理でも更新したり、また別のところでは参照したりしようとすると、
各処理において、stateになにが入っているのか、十分注意して実装することになる。
しかしそこに想定外の状態が入り込むとプログラムはバグってしまうわけだ。
もちろん、実際には変数のチェック処理を実装することで想定外の挙動を起こさないよう努力する。
しかしながら未知の値を持ちうる変数はできるかぎりプログラムから排除したい。
とはいえ状態を更新するような処理をきちんと記述できなければ書きたいプログラムを書けなくなる。
そこで登場するのが状態付き関数であり、Stateモナドである。と思う。

実装

pushとpop

まずは、リストを受け取り処理結果と処理後のリストを返すという形式で、
pushとpopを実装してみる。
入力したリストの中身を更新しないことに注意する。

push

def push(a):
    return lambda x: (None, [a] + x)

x = [1,2,3]
y = push(4)(x)
print(x)
print(y)

[1, 2, 3]　←push後でも中身は変わってないx
(None, [4, 1, 2, 3]) ←y

pop

def pop():
    return lambda x: (x[0], x[1:])

x = [1,2,3]
y = pop()(x)
print(x)
print(y)

[1, 2, 3] ← pop後も中身が変わってないx
(1, [2, 3]) ← y

それぞれの処理はラムダ式を返すことで関数をバインドできるようにし、
モナドに拡張できるようにしている。

def _bind(func):
    return lambda x: func(x)

_bind(push(4))([1,2,3])

(None, [4, 1, 2, 3])

_bind(pop())([1,2,3])

(1, [2, 3])

stateモナドへの拡張

pushとpopの処理はつくった。
ここで、スタックの例に戻ってみる。

stackExample :: State [Int] Int
stackExample = do
  push 1
  push 2
  push 3
  pop
  push 4
  x <- pop
  return x
> runState stackExample []
> (4,[2,1])

さて、自前でつくった push・pop を用いて、上記のようにスタック処理を記述できるだろうか？
このままではできない。
push・pop において入力と出力の形式が異なるからだ。

入力
[状態]
出力
(計算結果, [状態])

push pop を関数合成できるようにするためには、
両者の入力も出力も同じように抽象的に扱う仕組みが必要である。

入力
State ( , [状態])
出力
State (計算結果, [状態])

そこでいよいよStateモナドだ。

モナドクラス(仮)

class Monad():

    def __init__(self, a):
        raise NotImplementedError
        
    def _bind(self, func):
        raise NotImplementedError
        
    def __or__ (self, func):
        return self._bind(func)

    @staticmethod
    def call_state(s):
        return State(lambda : (s, s))

Stateモナド

class State(Monad):
    def __init__(self, a):
        self.run_state = a

    def _bind(self, func):
        _, s = self.run_state()
        return State(lambda :func(s)) 

    def __repr__(self):
        return  'State (%r, %r)' % self.run_state()

動かしてみる

Monad.call_state([1, 2, 3, 4])

State ([1, 2, 3, 4], [1, 2, 3, 4])

Monad.call_state([1, 2, 3, 4]) | pop()

State (1, [2, 3, 4])

Monad.call_state([1, 2, 3, 4]) | push(5)

State (None, [5, 1, 2, 3, 4])

Monad.call_state([1, 2, 3, 4]) | pop() | push(5)

State (None, [5, 2, 3, 4])

スタックの例

def stackExample(state):
    return state | push(1) \
                 | push(2) \
                 | push(3) \
                 | pop()   \
                 | push(4) \
                 | pop()

state = Monad.call_state([])
ret = stackExample(state)
print(state)
print(ret)

State ([], []) ← state
State (4, [2, 1]) ← ret

push と pop の処理を合成して元々の変数の値を変化させることなく、
状態更新を扱うことができた。

おわりに

以上のようにStateモナドを使うと

状態付き計算の関数合成ができる

ようだ。

個人的にはこの例を通じてStateモナドを書いてみて、
モナドを理解するうえでは、**"閉じている"**っていうのが重要なんだと思った。
モノイドとの関連もそれでより合点がいった。