Pythonでモナりたいとおもいます。
そして、モナドといえばMaybeが有名ですね。
Maybeは比較的わかりやすい上、色々な言語でも実用しやすいので自分で実装している人も
いたりするのではないかと思います。がしかし、
Stateモナドから理解したほうがいいんじゃないかなーと思うんだけど
というような記事を発見してしまいました。
ということで、Stateモナドを実装しようと思います。
Haskellでスタックを利用した加減乗除の計算機を作ってみる
Haskell の State モナド (1) - 状態を模倣する
第6回 局所的な「状態」を利用するためのStateモナド
とかを読んで意識を高めました。
これだけ既存記事があって今更という感も否めません。その上、参考記事をはじめとした説明は
具体的でわかりやすいものになっています。しかし、そのためにいかんせんスタックの実装部分に
力を入れすぎてしまい、いまいちStateの本質が掴みにくい感じがしました。
なので、ここは少し違う言語を使い自分で実装しなおしてみることで、より抽象的な仕組みとして
Stateモナドを把握することを目指しましょう。
Haskellでの定義
というわけで、ここではなるべく余計なことは考えずに、Haskellの実装を参考にして
とりあえずそのままPythonに移植してみることでStateモナドの本質的ななんかを会得したいと思います。
Pythonは動的型な言語ですが、わかりにくそうなところとかは、適時コメントで型の注釈とかを入れていきましょう。
それではHaskellの定義をみていきます。
newtype State s a = State { runState :: s -> (a, s) }
instance Monad (State s) where
return a = State $ \s -> (a, s)
m >>= k = State $ \s -> let
(a, s') = runState m s
in runState (k a) s'
定義を見た感じ、Stateはs -> (a, s)という関数を中身にもつモナドなようです。
sはState（状態）ですね。
返り値のタプルは、左のaが変更を加えた結果で、右のsが変更が加わった後の状態にあたります。
手続き型言語的な思考からすると、こいつにはちょっと奇妙な印象を受けますね！
ちなみに、Haskellの文法に詳しくない人のために説明すると、
Haskellではラムダ式の宣言を\ 引数 -> 式という形で行います。
また、letというキーワードはlet式というもので、let 以下で変数を束縛して
in以下の式が返るというようなものです。
Pythonにも欲しいですね（作りました http://qiita.com/hatchinee/items/1face0ffd5466de1ad97）。
そしてもう一つ、状態の取得と書き換えを行う関数の定義があります。
こちらはMonadStateという型クラスとして宣言されています。
class (Monad m) => MonadState s m | m -> s where
get :: m s
put :: s -> m ()
instance MonadState s (State s) where
get = State $ \s -> (s, s)
put s = State $ \_ -> ((), s)
Haskell力が低いので、型クラスってなんだよとかinstanceってOOPのアレ？ とか様々な疑問が
浮かんでは消えますが（* myuon_myonさんがコメントで解説してくれています。感謝！）
心を無にして関数の部分を翻訳します。
Stateの実装
とりあえずStateからいきましょう。
class State(object):
def __init__(self, a):
''' private '''
self.run_state = a
@classmethod
def ret(_, a):
''' return
'''
return State(lambda s: (a, s))
def bind(self, func):
''' >>=
'''
def _(a):
v, st = self.run_state(a)
return func(v).run_state(st)
return State(_)
def __rshift__(self, func):
''' define >> as bind '''
return self.bind(func)
runStateをself.run_stateメンバ
returnはPythonでは予約語なので、retというクラスメソッドとして宣言しておきます。
>>=はbindメソッドとして、あるいはなんか見た目が似たような感じなので>>という
演算子で利用出来るようにしておきます。
>>は別のMonad演算子で使うものだった気もするので、ヤバイと思ったら別のにするのもいいかと思います。
MonadStateの定義
class MonadState(object):
@classmethod
def get(_):
''' get = State $ \s -> (s, s)
'''
return State(lambda s: (s, s))
@classmethod
def put(_, a):
''' put s = State $ \_ -> ((), s)
'''
return State(lambda s: (None, a))
MonadStateです。Haskellでの定義をコメントにいれてみましたが、ほぼそのまま実装出来ていますね。
ではこれらの実装を使って、状態の書き換えと取得がうまくいくか確認してみます。
>>> (MonadState.put(12) >> (lambda _: \
MonadState.get())).run_state(13)
(12, 12)
>>> (MonadState.put(12) >> (lambda _: \
MonadState.get() >> (lambda i: \
MonadState.put(i * 2)))).run_state(13)
(None, 24)
プロンプトなり、doctestなりで実行するとうまくいくかと思います。
Stateモナドとは恐らく、関数の合成で手続きを抽象化しておいて、そこに状態を与えることで
結果や、あるいは状態への副作用を得ることが出来る機構なのだと思いました。
get, putの挙動やbindでの合成部分が複雑なので、理解に時間がかかるかもしれませんが
自分で実装してみたり、Stateを使ってなんかを作ってみたりすると何が起きているかは
心で感じ取れるようになってくると思います。
実践編
さて、なんとなく心で感じ取れてきたところで、今度はStateモナドを使ってなんかいいものを作ってみましょう。
スタックと言えばという事で逆ポーランド電卓を作ってみます。
とりあえず、文字列を演算子に変換したりする補助関数とかを定義しておきます。
from operator import add, sub, div, mul, concat
_OP_HOLDER = {
'+': add,
'-': sub,
'*': mul,
'/': div,
}
def _op(st):
op = _OP_HOLDER[st]
def _(x1, x2):
''' popの順番を制御しにくいので、ここで反転させる'''
print x2, st, x1
return [op(x2, x1)]
return _
def _concat(xs, ys):
print xs, ys
return concat(xs, ys)
def _is_valid_operator(v):
return v in ['+', '-', '*', '/']
次に、電卓へのプッシュ or 計算の部分を実装します。
class Calculator(object):
@classmethod
def push(_, val):
if _is_valid_operator(val):
return \
MonadState.get() >> (lambda x:
MonadState.put(
_concat(
x, _op(val)(x.pop(), x.pop()))))
else:
return \
MonadState.get() >> (lambda x:
MonadState.put(_concat(x, [val])))
@classmethod
def run(_, stk):
_, ret = stk.run_state([])
return ret.pop()
めんどうなので、popとかの部分は内部のリストに直接アクセスしてます。
テストしてみましょう。
if __name__ == '__main__':
C = Calculator
print '1 2 + 4 5 + *'
calc = \
C.push(1) >> (lambda _:
C.push(2) >> (lambda _:
C.push('+') >> (lambda _:
C.push(4) >> (lambda _:
C.push(5) >> (lambda _:
C.push('+') >> (lambda _:
C.push('*')))))))
assert C.run(calc) == (1 + 2) * (4 + 5)
'''
1 2 + 4 5 + *
[] [1]
[1] [2]
1 + 2
[] [3]
[3] [4]
[3, 4] [5]
4 + 5
[3] [9]
3 * 9
[] [27]
みたいにプリントされるはずだ！
'''
print '\n5 4 3 - +'
calc = \
C.push(5) >> (lambda _:
C.push(4)) >> (lambda _:
C.push(3)) >> (lambda _:
C.push('-')) >> (lambda _:
C.push('+'))
assert C.run(calc) == (5 + 4 - 3)
print '\n6 2 + 5 3 - 2 * /'
calc = \
C.push(6) >> (lambda _:
C.push(2) >> (lambda _:
C.push('+') >> (lambda _:
C.push(5) >> (lambda _:
C.push(3) >> (lambda _:
C.push('-') >> (lambda _:
C.push(2) >> (lambda _:
C.push('*') >> (lambda _:
C.push('/')))))))))
assert C.run(calc) == (6 + 2) / ((5 - 3) * 2)
どうでしょう。
逆ポーランド記法電卓を実装するのははじめてなので、うまく確信を持てないのですが
多分いい感じに動いているかと思います。
操作の部分は、高階関数を使っても使わなくても動きます。
高階関数を使えば、各操作の結果の集約を使って計算をしたりも出来たり(sumとか)しそうです。
Python書く上での、直接の実用性はなさそうですが頭の体操になって楽しかったです。
おつかれさまでした。
こういうのがお好きな方はこちらもどうぞ （今までに書いたPythonの黒魔術っぽいコーディングについての記事まとめ）