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

-   [2015/07/30/すごいE本をElixirでやる(17) - ヽ（´・肉・｀）ノログ](http://niku.name/articles/2015/07/30/%E3%81%99%E3%81%94%E3%81%84E%E6%9C%AC%E3%82%92Elixir%E3%81%A7%E3%82%84%E3%82%8B(17))
-   [2015/08/04/すごいE本をElixirでやる(18) - ヽ（´・肉・｀）ノログ](http://niku.name/articles/2015/08/04/%E3%81%99%E3%81%94%E3%81%84E%E6%9C%AC%E3%82%92Elixir%E3%81%A7%E3%82%84%E3%82%8B(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` というのもある．

```ex
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 で聞いてみた](https://groups.google.com/d/msg/elixir-lang-talk/U-cKQyWqwTY/Y9RgkfOeHgAJ) ら 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 へと変換できる．

```ex
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<sub>elixir</sub><sub>src</sub>.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](http://elixir-lang.org/docs/v1.0/mix/Mix.Tasks.Escript.Build.html) を見るのが一番正確だ．

[2014/07/17/Elixirでコマンドラインツールを作る](http://niku.name/articles/2014/07/17/Elixir%E3%81%A7%E3%82%B3%E3%83%9E%E3%83%B3%E3%83%89%E3%83%A9%E3%82%A4%E3%83%B3%E3%83%84%E3%83%BC%E3%83%AB%E3%82%92%E4%BD%9C%E3%82%8B) という簡単な解説を書いたこともある．

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

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

107 ページに

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

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

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