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

逆ポーランド記法電卓とたたみこみ(左)

rev_polish_foldl.hs

はじめに

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

準備

import Data.List
import Text.Read

演算子表

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

関数rpolish1

命令によって数値リストを更新する関数を作成する。

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

第1引数に数値リストを第2引数に命令をとり数値リストを返す。

数値リストがJustかNothingかでわける

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

数値リストがNothingならばNothingを返す。

演算子リストからの検索

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

演算子リストを検索して演算子だった場合とそうでなかった場合に処理をわける。

数値

演算子として解釈できない場合には数値としての解釈を試す。

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

数値として解釈できるなら数値リストの先頭に追加する。

演算子

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

数値リストに値がふたつ以上あればそれら2つに演算子を適用しリストにもどす。このとき数値の順序を入れ替える必要がある。

関数rpolish

foldl'にrpolish1を引数として与える。

rpolish :: [String] -> Maybe [Integer]
rpolish = foldl' rpolish1 $ Just []

出来上がり

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

rpolish :: [String] -> Maybe [Integer]
rpolish = foldl' rpolish1 $ Just []

まとめ

命令によって数値リストを更新するだけの関数をfoldl'で逆ポーランド記法電卓関数にすることができる。

課題

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

「逆ポーランド記法電卓」へもどる 「整数の列挙」へ

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