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

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

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

• Haskell 状態系モナド 超入門

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

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

ポーランド記法

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

中置記法と比較します。

中置記法	ポーランド記法	演算子の関数化
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 のように変化していると解釈できます。

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

• Clean 一意型 調査メモ 2014.12.05

共通化

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

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など）の受け渡しが明示的には記述されなくなります。裏で状態が受け渡されているため、本質的には書き換え前のコードと同じです。