すごいE本をElixirでやる(8章)

• 2015/07/30/すごいE本をElixirでやる(17) - ヽ（´・肉・｀）ノログ
• 2015/08/04/すごいE本をElixirでやる(18) - ヽ（´・肉・｀）ノログ

より．

8.1 逆ポーランド記法計算機

普段，計算では

演算子を数字の間に書く(2 + 2) / 5 のような書き方

をしている．他にもいくつか算術演算の記法がある．

前置表記法（ポーランド記法）と呼ばれるものは

演算子がオペランドの前にきます。この記法では、(2 + 2) / 5 は(/ (+ 2 2) 5) になります

となる．

逆ポーランド記法(RPN: Reverse Polish Notation)と呼ばれるものは

前置表記法の逆で、演算子がオペランドに続く形になります。先ほどの例はRPN では2 2 + 5 /となります

となる．

今回はこの RPN で計算を行う電卓を書く．Elixir で文字をトークンに分けるには String.split/1 が簡単だ．

String.split("10 4 3 + 2 * -") # => ["10", "4", "3", "+", "2", "*", "-"]

スタックを用意する，畳み込むのは Erlang と同じだ．
畳み込みには List.foldl/3 を使おう．

実際には Enum.reduce/3 というのがあって，List 以外にも Map や Set などの Enumerable に適用できるので良く使われる．

実は Enum.reduce/3 は第一引数が List の場合は List.foldl/3 を呼んでいる．
ただ，今回は「左(文字の先頭)から」ということを強調したいので List.foldl/3 を指定した．
「右から畳み込んでいく」 List.foldr/3 というのもある．

defmodule Calc do
  def rpn(x) when is_bitstring(x) do
    [result] = List.foldl(String.split(x), [], &rpn/2)
    result
  end

  defp rpn("+", [n1, n2 | stack]), do: [n2 + n1 | stack]
  defp rpn("-", [n1, n2 | stack]), do: [n2 - n1 | stack]
  defp rpn("*", [n1, n2 | stack]), do: [n2 * n1 | stack]
  defp rpn("/", [n1, n2 | stack]), do: [n2 / n1 | stack]
  defp rpn("^", [n1, n2 | stack]), do: [:math.pow(n2, n1) | stack]
  defp rpn("ln", [n | stack]), do: [:math.log(n) | stack]
  defp rpn("log10", [n | stack]), do: [:math.log10(n) | stack]
  defp rpn("sum", [n1, n2 | stack]) when is_number(n2), do: rpn("sum", [n1 + n2 | stack])
  defp rpn("sum", stack), do: stack
  defp rpn("prod", [n1, n2 | stack]) when is_number(n2), do: rpn("prod", [n1 * n2 | stack])
  defp rpn("prod", stack), do: stack
  defp rpn(x, stack), do: [read(x) | stack]

  defp read(x) do
    # try do
    #   String.to_float(x)
    # rescue
    #   ArgumentError -> String.to_integer(x)
    # end
    char_list = String.to_char_list(x)
    case :string.to_float(char_list) do
      {:error, :no_float} -> :erlang.list_to_integer(char_list)
      {float_value, _} -> float_value
    end
  end

  def rpn_test do
    5 = rpn("2 3 +")
    87 = rpn("90 3 -")
    -4 = rpn("10 4 3 + 2 * -")
    -2.0 = rpn("10 4 3 + 2 * - 2 /")
    :ok = try do
            rpn("90 34 12 33 55 66 + * - +")
          rescue
            MatchError -> :ok
          end
    4037 = rpn("90 34 12 33 55 66 + * - + -")
    8.0 = rpn("2 3 ^")
    true = :math.sqrt(2) == rpn("2 0.5 ^")
    true = :math.log(2.7) == rpn("2.7 ln")
    true = :math.log10(2.7) == rpn("2.7 log10")
    50 = rpn("10 10 10 20 sum")
    10.0 = rpn("10 10 10 20 sum 5 /")
    1000.0 = rpn("10 10 20 0.5 prod")
    :ok
  end
end

Calc.rpn("3 5 +")     # => 8
Calc.rpn("7 3 + 5 +") # => 15
Calc.rpn_test         # => :ok
Calc.rpn("1 2 ^ 2 2 ^ 3 2 ^ 4 2 ^ sum 2 -") # => 28.0

あれ String.to_integer("+") が 0 になるのは意図通りなのかな？
:string.to_integer('+') が {:error, :no_integer} になるのとは振舞いが異なるようだ．

elixir-talk で聞いてみた ら Erlang の方のバグでした．報告したのでそのうち直るかも．
今は Calc.read/1 では Erlang の to_float や to_charlist を使うことにする．

8.2 ヒースローからロンドンへ

入力として使うファイルを準備しましょう。ファイル操作には file モジュールが最適です。

Elixir でも File モジュールが用意されている．

だいたいの場合は File モジュールで完結させられるが，
凝ったことをやりたいなら File.open/2 で {:ok, io_device} が返るので，
この io_device を IO モジュールの第一引数として渡すと細かい制御を行える．

コードを読み込んだり，実行するなら Code モジュールを探すとよい．

• ファイルを開く: File.open/2
• ファイルを閉じる: File.close/1
• ファイルの中身を取得する: File.read/1
• ファイルの一行を読み込む: File.stream!/3 や IO.gets/2
• ポインタの位置を指定された場所に移動させる: Elixir には見つからなかったので，Erlang の :file.position/2 を使う？
• ファイルを開いて、Erlang項としてパースする: Code.eval_file/2
• 書き込む場所を変更して書き込む: Elixir には見つからなかったので，Erlang の :file.pwrite/2 を使う？

こんな感じかなあ．Elixir のモジュールで

• ポインタの位置を指定された場所に移動させる
• 書き込む場所を変更して書き込む

関数があれば教えてほしい．

一度にリストから3 つの要素を取り出す一般的で簡単な方法

Elixir では Enum.chunk/2 で N 個ずつの List へと変換でき，
また List.to_tuple/1 で List を Tuple へと変換できる．

defmodule Road do
  def main([file_name]) do
    doc = File.read!(file_name)
    parse_map(doc)
    |> optimal_path
  end

  # 文字列を読みやすい 3 要素のタプルのマップに変換する
  def parse_map(x) when is_list(x), do: List.to_string(x) |> parse_map
  def parse_map(x) when is_binary(x) do
    x
    |> String.split
    |> Enum.map(&String.to_integer/1)
    |> Enum.chunk(3)
    |> Enum.map(&List.to_tuple/1)
  end

  # 実際に問題を解く部分
  def shortest_step({a, b, x}, {{dist_a, path_a}, {dist_b, path_b}}) do
    opt_a1 = {dist_a + a, [{:a, a} | path_a]}
    opt_a2 = {dist_a + b + x, [{:x, x}, {:b, b} | path_b]}
    opt_b1 = {dist_b + b, [{:b, b} | path_b]}
    opt_b2 = {dist_a + a + x, [{:x, x}, {:a, a} | path_a]}
    # すべての Erlang 項は比較可能なことを思い出してください！
    # タプルの最初の要素が長さなので、このようにして並び替えできます。
    {min(opt_a1, opt_a2), min(opt_b1, opt_b2)}
  end

  # すごい Erlang 本方式，最適な経路を選ぶ
  def optimal_path(map) do
    {a, b} = List.foldl(map, {{0, []}, {0, []}}, &shortest_step/2)
    {_dist, path} = cond do
                      elem(a, 1) |> hd !== {:x, 0} -> a
                      elem(b, 1) |> hd !== {:x, 0} -> b
                    end
    Enum.reverse(path)
  end

  # optimal_path と同じ結果になるけど，こっちの方が僕にはわかりやすい
  def my_optimal_path(map) do
    {{dist_a, path_a}, {dist_b, path_b}} = List.foldl(map, {{0, []}, {0, []}}, &shortest_step/2)
    path = cond do
             dist_a < dist_b -> path_a
             dist_a > dist_b -> path_b
             # 同じ距離のときは {:x, 0} の含まれていない方を表示する
             dist_a === dist_b -> if Enum.member?(path_a, {:x, 0}), do: path_b, else: path_a
           end
    Enum.reverse(path)
  end
end

今回は作業の都合上ファイル名は orgmode_elixirsrc.exs となっている．

/Users/niku/projects/nikulog/2015/08/04% elixir -e 'IO.inspect Road.main(["road.txt"])' orgmode_elixir_src.exs
elixir -e 'IO.inspect Road.main(["road.txt"])' orgmode_elixir_src.exs
[b: 10, x: 30, a: 5, x: 20, b: 2, b: 8]

うむ．うまくいった．

Elixir でも，実行できるバイナリを作成する escript を利用できる．
作り方/使い方は Mix.Tasks.Escript.Build を見るのが一番正確だ．

2014/07/17/Elixirでコマンドラインツールを作る という簡単な解説を書いたこともある．

Road.optimal_path/1 の {:x, 0} と比較する方法が奇妙だなあと感じたけど，
Tuple の 1 番目の要素 distance で判断する方式だと，経路 A と B が同じ距離のときに，
「 {:x, 0} が入っていない方」という判定をしなくて良いというメリットがあるようだ．

だけど僕には my_optimal_path のようなロジックの方がわかりやすかった．結果は同じ……になるよね？

107 ページに

最短経路を選んだら、逆順に並び替えます（末尾再帰のお作法です。逆順にしなければいけません）

と書いてある．ここの foldl による式も末尾再帰と呼ぶのだろうか．

末尾再帰というのは，関数の最後に関数を呼び出して，スタックを増やさないような処理のことだと思っていた．