loading...
gumi TECH Blog

Elixir入門 09: 再帰

gumitech profile image gumi TECH Updated on ・3 min read

本稿はElixir公式サイトの許諾を得て「Recursion」の解説にもとづき、加筆補正を加えてElixirにおける関数の再帰呼び出しについてご説明します。

再帰によるループ

Elixirはデータがイミュータブルなので、他の関数型プログラミング言語と同じく、ループ処理の書き方は命令型プログラミング言語と異なります。たとえば、C#のような命令型言語では、配列要素の取り出しをつぎのように処理するでしょう。

for (i = 0; i < sizeof(array); i++) {
  array[i] = array[i] * 2;
}

上の例では配列とカウンタ変数のデータが書き替えられます。Elixirはイミュータブルですのでデータは変えられません。そこで、関数型言語では再帰を使うのです。関数がみずからを再帰的に呼び出してループさせるのです。呼び出ししない条件に達したとき、再帰が終わります。このやり方であれば、データが変わりません。

以下の関数はリストの要素数を数えて返します。関数はふたつの句を備え、引数でパターンマッチングされます。リストが空なら、ひとつ目の関数とマッチするので、0が返され再帰呼び出しはしません。これが終了条件になります。

リストに要素があれば、テイルを渡して再帰呼び出しし、その戻り値に1を加えます。つまり、再帰呼び出しされるたびに1ずつカウントアップされ、空になったとき再帰は止まって合計値が返されるのです。

defmodule Length do
  def of([]), do: 0
  def of([_ | tail]), do: 1 + of(tail)
end
iex> Length.of []
0
iex> Length.of [1, 2, 3]
3

なお、ふたつ目の関数でヘッドの変数は処理に使われません。使われない変数の頭にはアンダースコア_を添えるのがElixirの命名規則です。_で始まる変数に納めた値を取り出そうとすると警告が示されます。さらに、_のみを変数にしたとき、値の取り出しはコンパイルエラーになります。

iex> _x = 0
0
iex> _x
warning: the underscored variable "_x" is used after being set. A leading underscore indic
ates that the value of the variable should be ignored. If this is intended please rename t
he variable to remove the underscore

0
iex> _ = 1
1
iex> _
** (CompileError) iex:n: invalid use of _. "_" represents a value to be ignored in a patte
rn and cannot be used in expressions

reduceとmapのアルゴリズム

まず、前掲のリストの要素数が返される関数を手直しして、要素の数値を合計してみましょう。関数に数値の第2引数を加え、ヘッダでデフォルト値0を与えました。加算される合計値を引数で受け渡せば、イミュータブルは破りません。

ひとつ目の関数は、リストが空になったら引数の合計値を返して、再帰呼び出しは終わります。空でなかったらふたつ目の関数が、テイルと合計値を引数に再帰呼び出しして、ヘッドの値を加えます。つまり、つまり再帰のたびにヘッドの値を合計値に加えていくことになるのです。

defmodule Sum do
  def up(list, accumulator \\ 0)
  def up([], accumulator), do: accumulator
  def up([head | tail], accumulator),
    do: up(tail, head + accumulator)
end
iex> Sum.up([1, 2, 3])
6
iex> Sum.up([4, 5], 6)
15

リストから要素を順に取り出して、ひとつの値にまとめる処理はreduceアルゴリズムと呼ばれ、関数型プログラミングの重要な考え方のひとつです。

つぎは、リスト要素に処理を加えて、新たなリストにつくりかえます。つぎの関数はリスト要素の数値を2乗して、それらが要素に納められた新たなリストとして返します。なお、|はふたつのリストをひとつにつなげる演算子にもなるのです(「Elixir入門 04: パターンマッチング」「演算子によるパターンマッチング」参照)。このようにリスト要素を取り出して、新たなリスト要素に納めて返す処理はmapアルゴリズムと呼ばれます。

defmodule Sum do
  def square([]), do: []
  def square([head | tail]), do:
    [head * head | square(tail)]
end
iex> Sum.square([1, 2, 3])
[1, 4, 9]

再帰と末尾呼び出しの最適化はElixirの重要なポイントで、ループ処理をするときにも活用されます(末尾再帰参照)。もっとも、Elixirのプログラミングでは、リストの操作に再帰を用いることはほとんどないでしょう。

Enumモジュールに、リストで使える便利な機能がすでに用意されているからです。たとえば、関数Enum.reduce/3Enum.map/2はつぎのように用います。

iex> Enum.reduce([1, 2, 3], 0, fn(x, acc) -> x + acc end)
6
iex> Enum.map([1, 2, 3], fn(x) -> x * x end)
[1, 4, 9]

さらに、キャプチャ構文でもっと短くも書けます。

iex> Enum.reduce([1, 2, 3], 0, &+/2)
6
iex> Enum.map([1, 2, 3], &(&1 * &1))
[1, 4, 9]

Elixir入門もくじ

番外

Posted on by:

gumitech profile

gumi TECH

@gumitech

gumi TECH は、株式会社gumiのエンジニアによる技術記事公開やDrinkupイベントなどの技術者交流を行うアカウントです。 gumi TECH Blog: http://dev.to/gumi / gumi TECH Drinkup: http://gumitech.connpass.com

gumi TECH Blog

株式会社gumiのエンジニアによる技術記事を公開しています。

Discussion

pic
Editor guide