top page > computer > haskell > web_lecture > for_programmer > polish.html
更新日:
文責: 重城良国

ポーランド記法電卓

polish.hs

ポーランド記法とは

演算子を被演算子の前に書く記法だ。前置記法とも呼ぶ。2項演算子のみなら優先順位や丸括弧なしで演算が一意に定まる。

ウィキペディア: ポーランド記法

同じ意味の中置記法の式とポーランド記法の式だ。

(1 + 5) * (2 + 3)

* + 1 5 + 2 3

仕様

整数の四則演算のみとする。数値や演算子を文字列のリストとしてわたす。返り値は整数のリストのMaybe値だ。計算が完全に終われば1要素のみのリストとなる。演算子が足りず計算の途中ならば複数の整数がリストに残る。数値が足りず演算が実行できないときや文字列が演算子でも数値でもないときはNothing値を返す。

考えかた

演算子や数値を前に追加していったときの変化を示す。

演算子の追加

演算子の追加は数値リストの先頭ふたつへの演算の適用となる。結果は数値リストの先頭に追加される。

数値の追加

数値の追加は数値リストの先頭への数値の追加となる。

演算子の表

演算子の文字列表現と動作とを対応させる表を作る。

整数の2項演算なので動作はInteger型の値をふたつとりInteger型を返す関数だ。

Integer -> Integer -> Integer

文字列を鍵としこれを値とする辞書とする。演算子の数は4つとすくないのでリストによる辞書で良い。

operators :: [(String, Integer -> Integer -> Integer)]

定義

加減乗除のそれぞれについて文字列と動作とを対応させる。

operators = [("+", (+)), ("-", (-)), ("*", (*)), ("/", div)]

整数同士の演算なので除算には(/)ではなくdivを使用する。

関数polishの定義

準備

関数readMaybeを使うためにText.Readが必要だ。コードの先頭に置く。

import Text.Read

polish :: [String] -> Maybe [Integer]

基底部

基底として第1引数の文字列のリストが空である状態を考える。このとき演算は成功し数値リストは空となる。

polish [] = Just []

再帰部

まずは命令のリストをはじめの命令とそれ以外とにわける。

polish (s : ss) = ...

演算子リストから対応する演算の動作を探す。

lookup s operators

演算子リストに値が存在する場合と存在しない場合とに処理を分岐させる。

case lookup s operators of
Just o -> ...
_ -> ...

数値

演算子リストに値が存在しなければ値sは数値と考える。関数readMaybeは文字列が数値として読めればJust値をそうでなければNothingを返す。文字列sを数値に変換し数値リストの先頭に追加する。

_ -> case readMaybe s of
Just n -> maybe Nothing (Just . (n :)) $ polish ss
_ -> Nothing

maybe Nothing (Just . (n :)) $ polish ssがわかりにくいがこれはpolish ssの値がJust値ならnを追加しJust値として返し、NothingならばNothingを返す。ファンクターを学ぶともっときれいに書ける。Haskellにはコードをきれいにするためのギミックがたくさんある。それは単に構文論的な美しさではなく意味論的な(ry

演算子

演算子リストに値が存在したときは後続の命令の実行結果である数値リストの先頭のふたつに対して演算子の動作を適用する。後続の命令の実行が失敗していれば失敗(Nothing)を返す。

Just o -> case polish ss of
Just (x : y : ns) -> Just $ x `o` y : ns
_ -> Nothing

出来上がり

import Text.Read

operators :: [(String, Integer -> Integer -> Integer)]
operators = [("+", (+)), ("-", (-)), ("*", (*)), ("/", div)]

polish :: [String] -> Maybe [Integer]
polish [] = Just []
polish (s : ss) = case lookup s operators of
Just o -> case polish ss of
Just (x : y : ns) -> Just $ x `o` y : ns
_ -> Nothing
_ -> case readMaybe s of
Just n -> maybe Nothing (Just . (n :)) $ polish ss
_ -> Nothing

動かしてみる

% ghci polish.hs
*Main> polish ["+", "3", "8"]
11
*Main> polish ["*", "+", "1", "5", "+", "2", "3"]
30

コードの本質

エラー処理や複数の演算子への対応等の枝葉を除いたコードの本質は以下のようになる。足し算のみなら動くのでここまでのコードを理解するのが難しければ、以下のコードをまずは理解してみよう。

polish [] = []
polish ("+" : ss) = x + y : ns
where x : y : ns = polish ss
polish (s : ss) = read s : polish ss

まとめ

本質的な部分は単純だ。僕の性格上「複数演算子の使用」や「エラー処理」を入れないと気持ちが悪かったため、いろいろと複雑になってしまった。さらに学習が進むと同じコードをずっと簡潔に書ける。

「たたみこみ(左)」へもどる 「ポーランド記法電卓とたたみこみ(右)」へ

正当なCSSです! HTML5 Powered with CSS3 / styling, and Semantics