URL
試した環境
- Ubuntu Server 14.04 LTS
- Erlang/OTP 18
- Elixir 1.0.4
Loops through recursion
不変という特性のため、Elixir(や関数型言語)でのループは、は手続き型言語は異なる書き方をする。例えば、手続き型言語では次のように記述する。
for(i = 0; i < array.length; i++) {
array[i] = array[i] * 2
}
上の例では、配列と補助変数iを変更している。Elixirではこうはできない。その代わり、関数型言語は再帰に頼る。関数は停止条件に到達するまで再帰的に呼ばれ、動作する。任意の回数文字を出力する下記の例を考えてみる。
defmodule Recursion do
def print_multiple_times(msg, n) when n <= 1 do
IO.puts msg
end
def print_multiple_times(msg, n) do
IO.puts msg
print_multiple_times(msg, n - 1)
end
end
Recursion.print_multiple_times("Hello", 3)
caseと同様に、関数は複数の節を持つことができる。
関数への渡した引数が節の引数のパターンとマッチし、ガードの評価がtrueの場合に、その節が実行される。
$ elixir recursion.exs
Hello
Hello
Hello
print_multiple_times/2が最初に呼ばれた場合、引数のnは3である。
最初の節はnが1と同じか小さい時にこの定義を使うように言っている。
これにはマッチしないため、Elixirは次の節の定義に移る。
2番目の定義はガードがなくパターンにマッチするので、実行される。最初に msgが表示され、自分自身を呼び出し、第２引数に n-1つまり2を渡す。呼び出された関数では同様にmsgを表示し、n-1つまり1を第2引数に渡して、print_multiple_times/2を再び呼び出す。
nが1になったことにより、print_multiple_times/2にある第1定義のガードが評価されるので、この定義を実行する。msgを表示した後は、何も実行しない。
引数の2番目へどんな数を渡しても、第1の定義（ベースケースと呼ばれる）か、確実に1ステップ毎にベースケースに近づくような第2の定義のどちらかが呼ばれるprint_multiple_times/2を定義した。
Reduce and map algorithms
例えば、リストにある数の合計を求めるようなときに、再帰のちかをどのように使うか見てみる。
defmodule Math do
def sum_list([head|tail], accumulator) do
sum_list(tail, head + accumulator)
end
def sum_list([], accumulator) do
IO.puts accumulator
end
end
Math.sum_list([1,2,3], 0)
$ elixir math.exs
6
引数としてリスト[1,2,3]と初期値0を渡してsum_list/2を呼び出す。パターンマッチのルールに従ってマッチするものが見つかるまで、それぞれの節が試される。この場合、[1,2,3]は[head|tail]に対して、 head = 1, tail = [2,3]が割り当てられ、accumulatorには0がセットされる。
次にリストの先頭とアキュムレータを足し(head + accumulator)、リストの残り(tail)を第1引数にとしてsum_listを再び呼び出し、再帰的に処理する。
リストの残りは再びsum_listで、[head|tail]にマッチされ、リストが空になるまで、次のように続く。
sum_list([1, 2, 3], 0) # accumlator = 0(head)
sum_list([2, 3], 1) # accumlator = 1(head) + 0(accumlator)
sum_list([3], 3) # accumlator = 2(head) + 1(accumlator)
sum_list([], 6) # accumlator = 3(head) + 3(accumlator)
リストが空になると、最後の節にマッチし、最終結果の6が返る。
リストから値をとり１つの値へ減らしていく処理は、"reduce"アルゴリズムと呼ばれており、関数型プログラミングの中心となっている。
もし、リストに含まれる要素の値を2倍にしたければどうすればいいか。
iex> defmodule Math do
...> def double_each([head|tail]) do
...> [head * 2 | double_each(tail)]
...> end
...>
...> def double_each([]) do
...> []
...> end
...> end
iex> Math.double_each([1,2,3])
[2, 4, 6]
リストを再帰的にたどり、全ての要素を2倍にし、新しいリストを返す。
このリストの値とって、リストにマッピングする処理は、"map"アルゴリズムとして知られている。
再帰と末尾呼び出しの最適化はElixirの重要な部分で、ループを作るのよく利用される。
しかし、Elixirでプログラミングするときには、リストの操作として上記のような再帰を使うことはない。
Enumモジュールはリストで使える便利なものを既に提供している。例えば、上記の例は次のように書ける。
iex> Enum.reduce([1,2,3], 0, fn(x, acc) -> x + acc end)
6
iex> Enum.map([1,2,3], fn(x) -> x * 2 end)
[2, 4, 6]
キャプチャー構文を使えば次のように書ける
iex> Enum.reduce([1, 2, 3], 0, &+/2) # +演算子をキャプチャしている
6
iex> Enum.map([1, 2, 3], &(&1 * 2))
[2, 4, 6]