Stateモナドによるポーランド記法の処理

More than 3 years have passed since last update.

ポーランド記法の処理を例に、状態の取り扱い方を示します。初めにStateモナドを使わないで書いてから、Stateモナドを使って書き換えます。コードの変化を比較するのが狙いです。

この記事はHaskell 超入門シリーズの番外編です。特に以下の記事と関連しています。

この記事には姉妹編があります。


ポーランド記法

演算子を前置する記法です。演算子を関数化して括弧を取り払ったものだと見立てられます。

中置記法と比較します。

中置記法
ポーランド記法
演算子の関数化

1+2
+ 1 2
(+) 1 2

2+3*4
+ 2 * 3 4
(+) 2 ((*) 3 4)

2*3+4
+ * 2 3 4
(+) ((*) 2 3) 4

ポーランド記法では括弧を使わなくても優先順位が表現できます。


実装

ポーランド記法を文字列で渡して計算する処理を実装します。


分割

文字列をスペースで分割します。簡単のため、オペランドと演算子はスペースで区切られていることを前提とします。

eval src = words src

main = do
print $ eval "+ 1 2"


実行結果

["+","1","2"]



計算

演算子が来れば後ろの2つを見て計算します。

eval src = pn $ words src

pn ("+":x:y:_) = read x + read y
pn ("*":x:y:_) = read x * read y

main = do
print $ eval "+ 1 2"
print $ eval "* 1 2"


実行結果

3

2


再帰

複数の演算子を組み合わせた計算に対応するため、後ろのオペランドを再帰で処理します。単体の数字を評価するパターンを追加します。

eval src = pn $ words src

pn ("+":x:ys) = read x + pn ys -- 後ろのオペランドで再帰
pn ("*":x:ys) = read x * pn ys -- 後ろのオペランドで再帰
pn ( x:_ ) = read x -- 追加

main = do
print $ eval "+ 1 2"
print $ eval "* 1 2"
print $ eval "1"
print $ eval "+ 2 * 3 4"


実行結果

3

2
1
14


状態

後ろのオペランドはやりっ放しにできるので簡単ですが、前のオペランドだとどこまで処理したかを知る必要があります。未評価のまま残っているリストを返すように修正します。

eval src = fst $ pn $ words src

pn ("+":src1) =
let (x, src2) = pn src1
(y, src3) = pn src2
in (x + y, src3)
pn ("*":src1) =
let (x, src2) = pn src1
(y, src3) = pn src2
in (x * y, src3)
pn (x:src) = (read x, src)

main = do
print $ eval "+ 1 2"
print $ eval "* 1 2"
print $ eval "1"
print $ eval "+ 2 * 3 4"
print $ eval "+ * 2 3 4"


実行結果

3

2
1
14
10

評価するごとにリストが消費され、残りが後続の処理に渡されます。処理対象のリストを状態と見なせば、状態が src1 -> src2 -> src3 のように変化していると解釈できます。

uniqness.png

参考までに、このようなパターンはHaskellでは使われない一意型で顕著に表れます。


共通化

+* で同じ処理が重複しているため共通化します。

eval src = fst $ pn $ words src

op src1 f = -- 演算子処理の共通化
let (x, src2) = pn src1
(y, src3) = pn src2
in (f x y, src3)

pn ("+":src) = op src (+)
pn ("*":src) = op src (*)
pn ( x:src) = (read x, src)

main = do
print $ eval "+ 1 2"
print $ eval "* 1 2"
print $ eval "1"
print $ eval "+ 2 * 3 4"
print $ eval "+ * 2 3 4"


実行結果

3

2
1
14
10


Stateモナド

Stateモナドは状態を受け取って、値と更新された状態を返します。


  • 状態 → (値, 状態)

処理対象のリストを状態に見立て、Stateモナドを使って書き換えます。

import Control.Monad.State

eval src = evalState pn $ words src

op f = do
x <- pn
y <- pn
return $ f x y

pn = do
(x:xs) <- get
put xs
case x of
"+" -> op (+)
"*" -> op (*)
_ -> return $ read x

main = do
print $ eval "+ 1 2"
print $ eval "* 1 2"
print $ eval "1"
print $ eval "+ 2 * 3 4"
print $ eval "+ * 2 3 4"


実行結果

3

2
1
14
10

状態(srcなど)の受け渡しが明示的には記述されなくなります。裏で状態が受け渡されているため、本質的には書き換え前のコードと同じです。