ochalog

Ruby と MediaWiki が好きな電子・情報系の学生のブログ。

すごい E 本・第 8 章の逆ポーランド記法計算機

「すごい Erlang ゆかいに学ぼう!」第 8 章逆ポーランド記法RPN)計算機を打ち込んでみた。パターンマッチのおかげで簡潔に書けるのが好み。こういう例は、今まで自分が使ってきた言語ではどうしても長くなってしまいそう。

演習問題

いくつか演習問題があったので考えてみた。

まずは和 sum。6 章でやったように fold が使える。スタックとして使っているリストへの数の追加の順番を考えると foldr が自然だけれど、foldl にしてみた。加算は可換だから同じ結果になり、またマニュアルを見ると foldl は末尾再帰だから、こちらの方が速そう。

rpn("sum", Stack) ->
  [lists:foldl(fun(N, Sum) -> Sum+N end, 0, Stack)];

prod も同様。ちょうどこの前書いた SICP の問題の解答にもあった。初期値(単位元)が 1 であることに注意。

ochaochaocha3.hateblo.jp

rpn("prod", Stack) ->
  [lists:foldl(fun(N, Prod) -> Prod*N end, 1, Stack)];

badarith エラーを上げるようにする

pp. 100—101 の「NOTE」に書いてあること。よく分からない演算子やスタックに値が残ってクラッシュするときに、badarith エラーを上げるようにする。

まずはスタックに余分な値が残っているとき。rpn/1 を修正する。

rpn(L) when is_list(L) ->
  case
    lists:foldl(fun rpn/2, [], string:tokens(L, " "))
  of
    [Res] -> Res;
    _ -> erlang:error(badarith) % 追加
  end.

続いて、よく分からない演算子が見つかったとき。read/1list_to_integer に失敗することを利用すると、この場合を検出することができた。

read(N) ->
  case string:to_float(N) of
    {error,no_float} ->
      %% ここから追加
      try
        list_to_integer(N)
      catch
        error:badarg -> erlang:error(badarith)
      end;
      %% 追加ここまで
    {F,_} -> F
  end.

さらに演算子を追加する例

例えば階乗を追加してみたらどうか、と思ってやってみた。

rpn("fact", [N|S]) -> [factorial(N)|S];

log10 等と同様にスタックから取り出す数は 1 つ。長くなるので factorial は別に書いた。

%% 階乗関数
factorial(N) -> factorial(N, 1).

factorial(0, Acc) -> Acc;
factorial(N, Acc) when N > 0 ->
  factorial(N-1, N*Acc).

実行例。

14> calc:rpn("0 fact").
1
15> calc:rpn("3 fact").
6
16> calc:rpn("7 fact").
5040

まとめ

本からいろいろと追加した分を含めた calc.erl を載せておく。