search
LoginSignup
1

More than 5 years have passed since last update.

posted at

updated at

プログラミング Elixir 第七章

概要

プログラミング Elixir

リストを使った再帰関数の作り方を解説している章。

ヘッドとテイル

リストは空でなければ、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 関数を実装する。

sumhead + 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

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
What you can do with signing up
1