逆ポーランド記法の処理を例に、状態の取り扱い方を示します。初めに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的な側面が見えて来るのではないでしょうか。