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

• 2015/06/25/すごいE本をElixirでやる(11) - ヽ（´・肉・｀）ノログ
• 2015/07/01/すごいE本をElixirでやる(12) - ヽ（´・肉・｀）ノログ

より

5.1 再帰の動き

Elixir でも Erlang と同じように再帰を記述することができる．

defmodule Recursive do
  def fac(0), do: 1
  def fac(n) when n > 0, do: n * fac(n-1)

  def len([]), do: 0
  def len([_|t]), do: 1 + len(t)

  # Elixir では Erlang とは異なり \\ でデフォルト引数を宣言できる
  def tail_fac(0, acc), do: acc
  def tail_fac(n, acc \\ 1) when n > 0, do: tail_fac(n-1, n*acc)

  # もちろん Erlang の例と似たように，公開する関数と，内部で再帰する関数を分けることもできる
  # デフォルト引数は引数の数が異なる同名の関数がある場合に
  # どの呼び出しにマッチするか考えないといけないので，この公開用と内部用を分ける方が好き
  def tail_len(l), do: tail_len(l, 0)
  defp tail_len([], acc), do: acc
  defp tail_len([_|t], acc), do: tail_len(t, acc+1)
end

Recursive.fac(4) # => 24
Recursive.len([1,2,3,4]) # => 4
Recursive.tail_fac(4) # => 24
Recursive.tail_len([1,2,3,4]) # => 4

5.2 さらに末尾関数

再帰関数というのはErlang に存在する唯一のループ構造であり

はい．

複製 (duplicate) する関数は，Erlang の場合と異なり，引数の順序を「複製対象」「複製回数」とした．
Elixir の API 設計では第一引数に subject をもってくるというベストプラクティスのためである．

defmodule X do
  # duplicate
  def duplicate(term, 0), do: []
  def duplicate(term, n) when n > 0, do: [term|duplicate(term, n-1)]

  def tail_duplicate(term, n), do: tail_duplicate(term, n, [])
  defp tail_duplicate(term, 0, list), do: list
  defp tail_duplicate(term, n, list) when n > 0, do: tail_duplicate(term, n-1, [term|list])

  # reverse
  def reverse([]), do: []
  def reverse([h|t]), do: reverse(t) ++ [h]

  def tail_reverse(l), do: tail_reverse(l, [])
  defp tail_reverse([], acc), do: acc
  defp tail_reverse([h|t], acc), do: tail_reverse(t, [h|acc])

  # sublist
  def sublist(_, 0), do: []
  def sublist([], _), do: []
  def sublist([h|t], n) when n > 0, do: [h|sublist(t, n-1)]

  def tail_sublist(l, n), do: tail_reverse(tail_sublist(l, n, []))
  defp tail_sublist(_, 0, sl), do: sl
  defp tail_sublist([], _, sl), do: sl
  defp tail_sublist([h|t], n, sl) when n > 0, do: tail_sublist(t, n-1, [h|sl])

  # zip
  def zip([], []), do: []
  def zip([x|xs], [y|ys]), do: [{x, y}|zip(xs, ys)]

  def tail_zip(xs, ys), do: tail_reverse(tail_zip(xs, ys, []))
  defp tail_zip([], [], acc), do: acc
  defp tail_zip([x|xs], [y|ys], acc), do: tail_zip(xs, ys, [{x, y}|acc])

  # lenient_zip
  def lenient_zip([], _), do: []
  def lenient_zip(_, []), do: []
  def lenient_zip([x|xs], [y|ys]), do: [{x, y}|lenient_zip(xs, ys)]

  def tail_lenient_zip(xs, ys), do: tail_lenient_zip(xs, ys, [])
  defp tail_lenient_zip([], _, acc), do: acc
  defp tail_lenient_zip(_, [], acc), do: acc
  defp tail_lenient_zip([x|xs], [y|ys], acc), do: [{x, y}|tail_lenient_zip(xs, ys, acc)]

  # quicksort
  def quicksort([]), do: []
  def quicksort([pivot|rest]) do
    {smaller, larger} = partition(rest, pivot, [], [])
    quicksort(smaller) ++ [pivot] ++ quicksort(larger)
  end

  def partition([], _pivot, smaller, larger), do: {smaller, larger}
  def partition([h|t], pivot, smaller, larger) do
    if h <= pivot do
      partition(t, pivot, [h|smaller], larger)
    else
      partition(t, pivot, smaller, [h|larger])
    end
  end

  def lc_quicksort([]), do: []
  def lc_quicksort([pivot|rest]) do
    lc_quicksort(for smaller <- rest, smaller <= pivot, do: smaller)
    ++ [pivot] ++
    lc_quicksort(for larger <- rest, larger > pivot, do: larger)
  end
end

X.duplicate(:hoge, 0) # => []
X.duplicate(:hoge, 4) # => [:hoge, :hoge, :hoge, :hoge]
X.tail_duplicate(:hoge, 4) # => [:hoge, :hoge, :hoge, :hoge]

X.reverse([]) # => []
X.reverse([1,2,3,4]) # => [4, 3, 2, 1]
X.tail_reverse([1,2,3,4]) # => [4, 3, 2, 1]

X.sublist([1,2,3,4,5,6], 3) # => [1, 2, 3]
X.tail_sublist([1,2,3,4,5,6], 3) # => [1, 2, 3]

X.zip([:a,:b,:c], [1,2,3]) # => [a: 1, b: 2, c: 3]
X.tail_zip([:a,:b,:c], [1,2,3]) # => [a: 1, b: 2, c: 3]

X.lenient_zip([:a,:b,:c], [1,2,3,4,5]) # => [a: 1, b: 2, c: 3]
X.tail_lenient_zip([:a,:b,:c], [1,2,3,4,5]) # => [a: 1, b: 2, c: 3]

X.quicksort([5, 4, 9, 7, 1, 8, 3, 2, 6]) # => [1, 2, 3, 4, 5, 6, 7, 8, 9]
X.lc_quicksort([5, 4, 9, 7, 1, 8, 3, 2, 6]) # => [1, 2, 3, 4, 5, 6, 7, 8, 9]

5.3 リストを超えて

Elixir では subject を第一引数に取ることが多いので，
API の引数の順序を 木構造，キー，値 といった形式になるように変更した．

defmodule Tree do
  def empty, do: {:node, nil}

  def insert({:node, nil}, key, val) do
    {:node, {key, val, {:node, nil}, {:node, nil}}}
  end
  def insert({:node, {key, val, smaller, larger}}, new_key, new_val) when new_key < key do
    {:node, {key, val, insert(smaller, new_key, new_val), larger}}
  end
  def insert({:node, {key, val, smaller, larger}}, new_key, new_val) when new_key > key do
    {:node, {key, val, smaller, insert(larger, new_key, new_val)}}
  end
  def insert({:node, {key, _val, smaller, larger}}, new_key, new_val) when new_key === key do
    {:node, {key, new_val, smaller, larger}}
  end

  def lookup({:node, nil}, _key), do: :undefined
  def lookup({:node, {key, val, _smaller, _lager}}, key), do: {:ok, val}
  def lookup({:node, {node_key, _val, smaller, _lager}}, key) when key < node_key do
    lookup(smaller, key)
  end
  def lookup({:node, {node_key, _val, _smaller, lager}}, key) when key > node_key do
    lookup(lager, key)
  end
end

t1 = Tree.insert(Tree.empty, "Jim Woodland", "[e-mail]")
# {:node, {"Jim Woodland", "[e-mail]", {:node, nil}, {:node, nil}}}

t2 = Tree.insert(t1, "Mark Anderson", "[e-mail]")
# {:node,
#  {"Jim Woodland", "[e-mail]", {:node, nil},
#   {:node, {"Mark Anderson", "[e-mail]", {:node, nil}, {:node, nil}}}}}


addresses = t2
            |> Tree.insert("Wilson Longbrow", "[e-mail]")
            |> Tree.insert("Kevin Robert", "[e-mail]")
            |> Tree.insert("Anita Bath", "[e-mail]")
# {:node,
#  {"Jim Woodland", "[e-mail]",
#   {:node, {"Anita Bath", "[e-mail]", {:node, nil}, {:node, nil}}},
#   {:node,
#    {"Mark Anderson", "[e-mail]",
#     {:node, {"Kevin Robert", "[e-mail]", {:node, nil}, {:node, nil}}},
#     {:node,
#      {"Wilson Longbrow", "[e-mail]", {:node, nil}, {:node, nil}}}}}}}

Tree.lookup(addresses, "Anita Bath")
# {:ok, "[e-mail]"}

Tree.lookup(addresses, "Jacques Requin")
# :undefined

P63 にある図の 新 と 旧 は

次の図では、「E」を含むノードが追加され、これによって「E」より上のすべての親を更新する必要が出てきます。

という説明とは逆になっているように思える．

英語版を眺めてみたが， Recursion | Learn You Some Erlang for Great Good! だとこの挿絵はみつけられなかった．