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

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

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"

実行結果

計算

演算子が来ればスタックから値を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 +"

実行結果

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

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 +"

実行結果

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

共通化

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

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 +"

実行結果

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