すごいH本 part69

関数型問題解決法

関数型のテクニックを使ってエレガントに

逆ポーランド記法電卓

数式を書く方法として、逆ポーランド記法(reverse polish notation) 略してRPNがある。

RPNでは、演算子は数に挟まれず、数の後ろに書く。

4 + 3 が 4 3 + になる。

4と3を足してそれに10を掛ける場合は、4 3 + 10 * となる。 また、4 3 + は 7 なので、7 10 * と等価になる。

RPN記法の式を計算する方法。

数のスタックをイメージする。左から右に計算式を読む。 数を読み込んだらそれをスタックの1番目に積む(push)。 演算子を読み込んだら、スタックの1番目から2つの数を取り出し(pop) その2つの数に演算子を施して、演算結果をスタックに積み直す。

式の末尾にたどり着いたら、計算結果が出る。

これを Haskell で実装する

• 関数の型を考える
  • 型シグネチャ
• 入力の文字列をリストに分割できないか考える
• リストをどうやって処理するか考える
  • 左畳み込み
• スタックをどう表現するか考える
  • リスト

solveRPN :: String -> Double
solveRPN = head . foldl foldingFunction [] . words
    where foldingFunction (x:y:ys) "*" = (y * x):ys
          foldingFunction (x:y:ys) "+" = (y + x):ys
          foldingFunction (x:y:ys) "-" = (y - x):ys
          foldingFunction xs numberString = read numberString:xs

実行

*Main> solveRPN "10 4 3 + 2 * -"
-4.0
*Main> solveRPN "2 3.5 +"
5.5

演算子を増やす

solveRPN :: String -> Double
solveRPN = head . foldl foldingFunction [] . words
    where foldingFunction (x:y:ys) "*" = (y * x):ys
          foldingFunction (x:y:ys) "+" = (y + x):ys
          foldingFunction (x:y:ys) "-" = (y - x):ys
          foldingFunction (x:y:ys) "/" = (y / x):ys
          foldingFunction (x:y:ys) "^" = (y ** x):ys
          foldingFunction (x:xs) "ln" = log x:xs
          foldingFunction xs "sum" = [sum xs]
          foldingFunction xs numberString = read numberString:xs

実行

*Main> solveRPN "2.7 ln"
0.9932517730102834
*Main> solveRPN "10 10 10 10 sum 4 /"
10.0
*Main> solveRPN "10 10 10 10 10 sum 4 /"
12.5
*Main> solveRPN "10 2 ^"
100.0

所感

0 除算すると

*Main> solveRPN "10 0 /"
Infinity

こんな感じになる。Infinity とは。

where での処理のまとめかたとパターンマッチは参考になった。

すごいHaskellたのしく学ぼう！