概要
リストを使った再帰関数の作り方を解説している章。
ヘッドとテイル
リストは空でなければ、head と tail によって構成されている。head は値、tail はリストになっている。また、head と tail はパイプ文字 | で分けて表すことができる。
[2] を head と tail で分けて表すと [2 | []] となる。
iex> [2 | []] == [2]
true
[1, 2] を分けて表すと [1 | [2]] と分けることができ、さらに上記から
iex> [1 | [2 | []]] == [1, 2]
true
となることがわかる。
パターンの中でもパイプ文字は使うことができ、以下の様に head と tail を分けて取得できる。
iex> [head | tail] = [1, 2, 3]
[1, 2, 3]
iex> head
1
iex> tail
[2, 3]
head と tail を再帰に利用する
パイプ文字で head と tail を取得できる機能を使って再帰関数を作成することができる。
defmodule Sample do
def list_sum([]), do: 0
def list_sum([head | tail]), do: head + list_sum(tail)
end
iex> Sample.list_sum([1, 2, 3])
6
iex> Sample.list_sum([])
0
引数のリストが空でない間は 2 つめのパターンにマッチし続けて、最後に 0 を返す。
map 関数の作成
リストと関数を引数に取り、渡されたリストの各要素に関数を適用させる map 関数を作成する。
defmodule Sample do
def map([], _func), do: []
def map([head | tail], func), do: [func.(head) | map(tail, func)]
end
渡した func 関数を head に適用していって、リストが空になったら空のリスト返す。
最初の定義では func が使われないので _ を付けて使わないことを明示する。
iex> Sample.map [1, 2, 3, 4], fn (n) -> n * n end
[1, 4, 9, 16]
iex> Sample.map [1, 2, 3, 4], fn (n) -> n + 1 end
[2, 3, 4, 5]
iex> Sample.map [1, 2, 3, 4], fn (n) -> n + n end
[2, 4, 6, 8]
& ショートカットを使うこともできる。
iex> Sample.map [1, 2, 3, 4], &(&1 + &1)
[2, 4, 6, 8]
再帰中の値の保持
足し算の合計を再帰で計算する際など、途中の合計を保持したい場合に、引数に状態を渡す方法で実現する。
defmodule Sample do
def sum([], total), do: total
def sum([head | tail], total), do: sum(tail, head + total)
end
iex> Sample.sum([1, 2, 3, 4, 5], 0)
15
iex> Sample.sum([11, 12, 13, 14, 15], 0)
65
しかし、この方法で実装した場合、最初に必ず無駄な引数である 0 を渡さなければならず、あまりうれしくない。そこで、リストを受け取る関数を public にし、実際の処理を private で定義する。
defmodule Sample2 do
def sum(list), do: _sum(list, 0)
defp _sum([], total), do: total
defp _sum([head | tail], total), do: _sum(tail, head + total)
end
iex> Sample2.sum([1, 2, 3, 4, 5])
15
iex> Sample2.sum([11, 12, 13, 14, 15])
65
実際の処理を private にして外から呼び出せない様にし、public な関数に _ を付けた名前にすることで、sum と _sum に関連があることを人が見てもわかる様にしている。
sum 関数の一般化
map の例と同じように sum を一般化した reduce 関数を実装する。
sum の head + total の部分を関数を適用するようにし、さらに map 関数でみたように関数を渡せるようにしてあげれば良い。
defmodule Sample do
def reduce([], value, _), do: value
def reduce([head | tail], value, func), do: reduce(tail, func.(head, value), func)
end
iex> Sample.reduce([1, 2, 3, 4, 5], 0, &(&1 + &2))
15
iex> Sample.reduce([1, 2, 3, 4, 5], 1, &(&1 * &2))
120
複雑なリストのパターン
リストは、複数の要素をパイプ文字の左におくこともできる。
iex> [1, 2 | [3, 4]]
[1, 2, 3, 4]
そのため、以下の様に head を個別にマッチさせることもできる。
iex> [a, b | c ] = [1, 2 | [3, 4]]
[1, 2, 3, 4]
iex> a
1
iex> b
2
iex> c
[3, 4]
これを利用して、リスト内の値のペアをスワップする関数を実装する。
defmodule Sample do
def swap([]), do: []
def swap([a, b | tail]), do: [b, a | swap(tail)]
def swap([_]), do: raise "Can't swap a list with an odd number of elements"
end
iex> Sample.swap([1, 2, 3, 4])
[2, 1, 4, 3]
iex> Sample.swap([])
[]
iex> Sample.swap([1, 2, 3])
** (RuntimeError) Can't swap a list with an odd number of elements
iex:45: Sample.swap/1
iex:44: Sample.swap/1
リストのリスト
[id, class, name, sex] の属性を持った生徒のデータがあった際に、class が 6 の値を持った生徒のデータを取り出したいとする。
students = [
[1, 1, 'taro', 'man'],
[2, 1, 'hanako', 'woman'],
[3, 2, 'jiro', 'man'],
[4, 6, 'saburo', 'man'],
[5, 3, 'hanae', 'woman'],
[6, 2, 'shiro', 'man'],
[7, 6, 'hanami', 'woman'],
[8, 5, 'hanaka', 'woman'],
[9, 6, 'goro', 'man']
]
defmodule Student do
def fetch_class_6([]), do: []
def fetch_class_6([[id, 6, name, sex] | tail]), do: [[id, 6, name, sex] | fetch_class_6(tail)]
def fetch_class_6([_ | tail]), do: fetch_class_6(tail)
end
iex> Student.fetch_class_6(students)
[[4, 6, 'saburo', 'man'], [7, 6, 'hanami', 'woman'], [9, 6, 'goro', 'man']]
このままだと class の値が 6 のデータしか取得できないので、好きな class を指定できる様にする。
defmodule Student do
def fetch_by_class([], class_num), do: []
def fetch_by_class([[id, class_num, name, sex] | tail], class_num), do: [[id, class_num, name, sex] | fetch_by_class(tail, class_num)]
def fetch_by_class([_ | tail], class_num), do: fetch_by_class(tail, class_num)
end
iex> Student.fetch_by_class(students, 6)
[[4, 6, 'saburo', 'man'], [7, 6, 'hanami', 'woman'], [9, 6, 'goro', 'man']]
iex> Student.fetch_by_class(students, 5)
[[8, 5, 'hanaka', 'woman']]
iex> Student.fetch_by_class(students, 1)
[[1, 1, 'taro', 'man'], [2, 1, 'hanako', 'woman']]
[id, class_num, name, sex] が複数回出てくるのと、id, name, sex は要素数をチェックしているだけで、特に関数内で使用されないため、少しリファクタリングすると次のようになる
defmodule Student do
def fetch_by_class([], class_num), do: []
def fetch_by_class([head = [_, class_num, _, _] | tail], class_num), do: [head | fetch_by_class(tail, class_num)]
def fetch_by_class([_ | tail], class_num), do: fetch_by_class(tail, class_num)
end