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

ポーランド記法とたたみこみ(右)

polish_foldr.hs

はじめに

ポーランド記法電卓関数polishは関数foldrで書ける。関数foldrで書けば再帰(くりかえし)のことを考えずにすむ。新しく追加された値と今まで計算してきた値とからの新たな値の生成に集中できる。

準備

import Text.Read

演算子の表

演算子の表は前回と同じだ。

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

関数polish1

命令リストに追加された値と数値リストの古い値とから数値リストの新しい値を求める関数を作成する。

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

命令ひとつとそのときの数値リストとをとり新たな数値リストを返す。

Maybe値による場合わけ

第2引数の数値リストがJustの場合とNothingの場合とで場合わけをする。

polish1 s (Just ns) = ...
polish1 _ _ = Nothing

数値リストがNothingならば新しい数値リストもNothingとなる。

演算子の検索

関数lookupで演算子リストのなかから演算子名を鍵として演算動作を検索する。

polish1 s (Just ns) = case lookup s operators of
Just o -> ...
_ -> ...

数値

演算子リストのなかに一致する文字列がなかったとき数値としての解釈を試す。

_ -> maybe Nothing (Just . (: ns)) $ readMaybe s

数値として解釈できるならば数値リストnsの先頭に解釈した値を追加しJust値として返す。そうでなければNothingを返す。

演算子

演算子リストから演算動作が取り出せたなら数値リストにすくなくとも2要素の数値が存在することを確認しその2要素に演算を適用し数値リストにもどす。

Just o -> case ns of
x : y : ns' -> Just $ x `o` y : ns'
_ -> Nothing

2要素以上の数値がなければNothingを返す。

関数polish

関数polish1はひとつの命令と残りの命令を実行した結果をとり新しい結果を返す関数だ。これをfoldrに与えることで関数polishができる。

polish :: [String] -> Maybe [Integer]
polish = foldr polish1 (Just [])

まとめ

古い値から新しい値を作ることに集中し再帰の部分をfoldrにまかせることで、一度に考えることをすくなくすることができる。実装が簡単になりバグも減らせる。

課題

  1. Bool値と整数のタプルのリストをとってしたのルールで計算する関数を作成せよ
  2. 1を生の再帰で解答したなら関数foldrを使って、関数foldrで解答したなら生の再帰を使って書き直せ

「ポーランド記法電卓」へもどる 「逆ポーランド記法電卓」へ

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