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

More than 3 years have passed since last update.

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

この記事は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","+"]



数字

逆ポーランド記法はスタックで処理します。

数字が来ればスタックに積みます。ソースが空になればスタックから値を取り出して返します。

eval src = rpn (words src) []

rpn :: [String] -> [Int] -> Int
rpn (x:src) stack = rpn src $ read x : stack -- 数字を積む
rpn [] (x:_) = x -- 値を返す

main = do
print $ eval "1"


実行結果

1



計算

演算子が来ればスタックから値を2つ取り出して、計算結果をスタックに積みます。



  • y:x:stack(x + y):stack

eval src = rpn (words src) []

rpn :: [String] -> [Int] -> Int
rpn ("+":src) (y:x:stack) = rpn src $ x + y : stack -- 追加
rpn ("*":src) (y:x:stack) = rpn src $ x * y : stack -- 追加
rpn ( x:src) stack = rpn src $ read x : stack
rpn [] ( x:_ ) = x

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


実行結果

1

3
2
14
10

ネストした計算にも対応できます。状態の受け渡しを細かく管理しなくて済むため、ポーランド記法よりも楽です。


Stateモナド

スタックを状態として見なせばStateモナドで表現できます。


アクション

Stateモナドで表現されたスタックを直感的に使用するため、スタックを操作するStateアクションを実装します。

今までのコードとは切り離した単独実装として示します。

import Control.Monad.State

push x = modify (x:)
pop = do
(x:xs) <- get
put xs
return x

test = do
push 3
push 5
push 4
pop

main = do
print $ runState test []


実行結果

(4,[5,3])



修正

逆ポーランド記法の処理を、Stateモナドによるスタック操作を使って書き換えます。

import Control.Monad.State

push x = modify (x:)
pop = do
(x:xs) <- get
put xs
return x

eval src = evalState (rpn (words src)) []

rpn ("+":src) = do
y <- pop
x <- pop
push $ x + y
rpn src

rpn ("*":src) = do
y <- pop
x <- pop
push $ x * y
rpn src

rpn (x:src) = do
push $ read x
rpn src

rpn [] = pop

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


実行結果

1

3
2
14
10

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


共通化

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

import Control.Monad.State

push x = modify (x:)
pop = do
(x:xs) <- get
put xs
return x

eval src = evalState (rpn (words src)) []

op f = do
y <- pop
x <- pop
push $ f x y

rpn ("+":src) = op (+) >> rpn src
rpn ("*":src) = op (*) >> rpn src
rpn ( x:src) = push (read x) >> rpn src
rpn [] = pop

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


実行結果

1

3
2
14
10

rpnはStateモナド使用前よりもかなりシンプルです。opと合わせて見れば、スタック操作を抽象化して手続的に書くことによる、モナドのDSL的な側面が見えて来るのではないでしょうか。