Elixir（関数型言語）で再帰関数を作る方法

いきなりまとめ

公式サイトのガイドより。

再帰関数を作るアルゴリズムは2通り

• MAPアルゴリズム
• REDUCEアルゴリズム

Enumモジュールを使えば再帰関数は簡単に実装可能。

背景

なぜ再帰関数が必要か？
関数型言語の変数はimmutable（変更不可）だから。
ループ処理(for,while,etc)で前回の値を使用して次回の値をアップデートしていく場合には再帰関数を作る必要がある。
        for(i = 0; i < sizeof(array); i++) {
          array[i] = array[i] * 2;
        }

 関数型言語はなぜimmutableか？
 参照透過的であるため。

 参照透過性とは何か？
 f(x)→yにおいてxが定数で置き換え可能であること。
 非関数型言語でxの値を代入により次々にアップデートしていくと置き換えは不可能。

なぜ参照透過性が必要か？
コードのメンテナンス性を向上させるため。
同じ変数を次々にアップデートしていくと、どの段階の処理に問題があるか検証に時間が掛かる。

Today I Learned

関数型言語において再帰関数を作る方法は主に2つ。
REDUCEアルゴリズムとMAPアルゴリズム。

REDUCEアルゴリズム

引数リストの要素を関数の呼び出しごとにpop、
popされ要素が減ったリストを引数として再帰的に関数を呼び出す。
たとえば、[1,2,3]の総和を求めたい。

#
# 1:引数パターンによって同名関数のマッチング
#    リストの長さ≠0　→　def sum_list([head | tail], accumulator)
#    リストの長さ=0　→　def sum_list([], accumulator)
#
# 2:リスト要素のパターンマッチング
#     [head|tail]で引数リストを先頭の1要素とそれ以外の要素とにわけheadとtailにマッチさせる
#
# 3:関数の再帰呼び出し
#
defmodule Math do
  def sum_list([head | tail], accumulator) do
    sum_list(tail, head + accumulator)
  end

  def sum_list([], accumulator) do
    accumulator
  end
end

IO.puts Math.sum_list([1, 2, 3], 0) #=> 6

MAPアルゴリズム

引数リストの要素を関数の呼び出しごとにpop、
popされた要素に処理を加え、
popされ要素が減ったリストを引数として自己関数を呼び出す。
各回の関数の呼び出しでは上記の先頭要素と後続要素を結合したリストを返す。
たとえば、[1,2,3]の各要素を2倍にする場合。

defmodule Math do
  def double_each([head | tail]) do
    [head * 2 | double_each(tail)]
  end

  def double_each([]) do
    []
  end
end

IO.puts Math.double_each([1, 2, 3]) #=> [2, 4, 6]



Enumモジュール

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]