田舎で並行処理の夢を見る

試したこと、需要がないかもしれないけど細々とアウトプットしてます

【サンプルコード多数あり】Reduce関数の基礎と考え方

関数型言語での繰り返し処理

関数型言語には基本的に繰り返し分(for文)と呼ばれる文法は用意されておりません。では、例えば以下のような処理をどのように行うのでしょうか。

  • 配列の要素を1つずつ取り出し2倍にする
  • 上記の処理の結果から5以上の値を取り除く

Pythonでシンプルに記述するとこんな感じになるでしょうか(あえて内包表記は使っていません)。

data = [n for n in range(1, 11)]

# 要素の値を2倍に
double_result = list()
for n in data:
  double_result.append(n * 2)

print(double_result)
# [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

# 2倍した要素で10より大きい要素を除去
filter_result = list()
for n in double_result:
  if n < 10:
    filter_result.append(n)
    
print(filter_result)
# [2, 4, 6, 8]

ElixirではEnumに実装されたmap, filterを使うのがシンプルで良いでしょう。
mapは第1引数に指定されたデータ型の各要素に、第2引数で指定された処理(関数)を適応していきます。戻り値は第1引数で受けたデータ型と同じサイズのリスト(配列)になります。
それに対してfilterは第2引数に条件式(関数)を受け取り、trueの判定になった要素のみを持つリスト(配列)を返します。そのため、第1引数で受けたデータ型とリスト(配列)の要素数が異なる可能性があります。

data = Enum.map(1..10, fn n -> n end)

# map: 各要素を2倍に
Enum.map(data, fn n -> n * 2 end)
|> IO.inspect() # [2, 4, 6, 8, 10, 12, 14, 16, 18, 20]

# filter: 10より大きい要素を除去
|> Enum.filter(fn n -> n < 10 end)
|> IO.inspect() # [2, 4, 6, 8]

ElixirEnumにおけるmapfilterの詳しい解説は以下の記事でしておりますので、ご参照下さい。
www.okb-shelf.work

なぜreduceが必要なのか

先ほどのmapfilterの戻り値がリスト(配列)であることに気づかれたでしょうか。Elixirではmap, filterに対して列挙型と呼ばれる3種類のデータ型を第1引数に渡すことが出来ますが、どのデータ型の場合であっても戻り値はリスト(配列)になります。

勘の良い方はすでにお気づきでしょうが、このままでは恐ろしく不便なのです。例えば、受け取ったリストを先ほどのように各要素を2倍して10より大きい値を取り除いたところで、残ったリストの合計値を算出したい場合にどうすれば良いでしょうか。

map, filterではどう工夫をしても戻り値はリストであり、要素を1つずつ列挙する動きを取るため、合計値を算出してinteger型の戻り値を得ることは不可能です。このような場合に便利なのがreduceと呼ばれる処理(関数)になります。

先に種明かしをしておくと、reduceとは受け取ったデータ型を任意のデータ型に変換するための処理です。

前提知識: アキュムレーター(accumulator)について

reduce関数の動き方が分からないという方はアキュムレーターと呼ばれる関数型言語特有の概念、というか処理方法を知らないためでしょう。後に説明しますが、値が不変であることを約する必要がある関数型言語では処理した値を次の繰り返し処理に渡すためにちょっとした工夫をするのです。これがアキュムレーターと呼ばれるものになります。

アキュムレーター(accumulator)
意味: 蓄積者、蓄財家、蓄電池、累算器

関数型言語の多くはreduce関数の実装に再帰関数が用いられています。再帰関数は終了条件に一致しない場合に自分自身(関数)を呼び出します(再帰) 。ただ、何も考えずに再帰関数を書いてしまうと、リストの合計値などは求めることが出来ません。

defmodule Sample do
  # 配列が空の場合にhit
  def recursive([]), do: :ok
  # まだ要素がある場合にhit
  # eg: head=1, tail=[2,3,4,5]
  def recursive([head | tail]) do
    IO.puts("pivod: #{head}")
    recursive(tail)
  end
end

Sample.recursive([1,2,3,4,5])
# pivod: 1
# pivod: 2
# pivod: 3
# pivod: 4
# pivod: 5

この動きはmapと非常に似ています。適応している処理はIO.puts()であり、取得した先頭の要素を出力しています。

# アキュムレーターなしの再帰関数とmapの動き方は似ている
Enum.map([1,2,3,4,5], fn n -> IO.puts("pivod: #{n}") end)
# pivod: 1
# pivod: 2
# pivod: 3
# pivod: 4
# pivod: 5

mapはリストを受け取ってリストを返すように、このアキュムレーターなしの再帰関数では合計値を求めることは出来ません。 (Pythonで同じような状況を再現してみました)

def sample():
  lst_data = [1,2,3,4,5,6,7,8]
  for num in lst_data:
    sum_num = 0
    sum_num += num
  
  return sum_num
  
print(sample()) #result: 8

ではこの再帰関数にアキュムレーターを追加してあげます。一種のテクニックに近いものですので、まずはコードをご覧ください。
elixir

defmodule Sample do
  # 第2引数にaccumlatorを追加
  def sum([], accum), do: accum
  def sum([head | tail], accum) do
    # 再帰する際に第2引数に値を記録
    sum(tail, head + accum)
  end
end

# 第2引数に合計値(integer)の初期値となる0を指定
Sample.sum([1,2,3,4,5], 0) |> IO.puts()
# 15

種明かしをすると、取得したリストの先頭要素を第2引数の値に加算を繰り返しているだけです。こうすることで次の呼び出し時にアキュムレーターの値が1つ前の要素によって加算された値に更新されている状態になります。

# accumlatorの変化
# 1回目 0 + 1
# 2回目 0 + 1 + 2
# 3回目 0 + 1 + 2 + 3
# 4回目 0 + 1 + 2 + 3 + 4
# 5回目 0 + 1 + 2 + 3 + 4 + 5

このようにreduce関数では第2引数に対して最終的に変換したい値の型の初期値となる値(もしくは同じ型で要素をすでに持つもの)を渡します。例えば、最終的に得たいデータ型がリストであっても、アキュムレーターinteger型の値を用いてreduce関数を実行することは出来ますが個人的には非推奨です。アキュムレーターの初期値として与えた型と同じデータ型が戻り値となるという方が健全であり、結果が自明です。

Elixirのreduce関数

ElixirEnumには引数の数が異なる2つのreduce/2, reduce/3が用意されています。スタンダートとなるものはreduce/3の方で(列挙型, アキュムレーター, 関数)を受け取ります。reduce/2ではアキュムレーターの指定をする必要がなく、第1引数の値の最初の要素が自動的にアキュムレーターとして扱われます。

data = Enum.map(1..10, fn n -> n end)

# reduce/2 の場合
Enum.reduce(data, fn n, acc -> n + acc end) |> IO.puts()
# 55

# reduce/3 の場合
Enum.reduce(data, 0, fn n, acc -> n + acc end) |> IO.puts()
# 55

reduce/2は第1引数に指定された列挙型が空の場合にerrorになるのでreduce/3をメインで使うことをオススメします。

# reduce/2 の場合
Enum.reduce([], fn n, acc -> n + acc end) |> IO.puts()

** (Enum.EmptyError) empty error...

reduce関数を使ったサンプル

じゃあ何ができるかという話になるので3つぐらいサンプル置いときます

レベル1: シンプルな集計

リストの要素の合計を求める

すでにEnum.sum()という関数が用意されていますが、せっかくなのでreduceを使って記述してみます。

data = Enum.map(1..10, fn n -> n end)

# リストの要素の合計値を算出
Enum.reduce(data, 0, fn n, acc -> acc + n end)
|> IO.puts() # 55

アキュムレーターとして第2引数に渡しているのはinteger型の初期値である0です。

リストの要素の最大値を求める

こちらもEnum.max()という関数が実装されてはいますが、せっかくなので。

data = Enum.map(1..10, fn n -> n end)

# リストの要素の合計値を算出
Enum.reduce(data, 0, fn n, acc ->
  # 要素の値がaccを超えた際にaccを入れ替え
  # accには常に最大値が記録され続ける
  if n > acc do
    n
  else
    acc
  end
end)
|> IO.puts() # 10

レベル2

リストの重複する要素を取り除く

filter関数使うのでは?と思いきや、filterでは自身以外の要素を参照することは出来ないため、使うのはreduce関数になります。戻り値としてリストを返す必要があるのでアキュムレーターには空のリストを渡します。

こちらに関してもEnum.uniq()を使えば一瞬で終わる処理です。

data = [1, 2, 1, 3, 4, 5, 3, 6, 7, 8, 4, 9, 3, 6, 8]

# リストの要素の合計値を算出
Enum.reduce(data, [], fn n, acc ->
  if n in acc do
    acc
  else
    acc ++ [n]
  end
end)
|> IO.inspect()
# [1, 2, 3, 4, 5, 6, 7, 8, 9]

2次元リストを1次元リストに変換

lst_data = [
  [1,2,3],
  [4,5,6],
  [7,8,9]
]

res = Enum.reduce(lst_data, [], fn data, accum -> accum ++ data end)
IO.inspect(res)
#result: [1, 2, 3, 4, 5, 6, 7, 8, 9]

List.flatten()でも同じ処理をすることが可能ですが、List.flatten()の場合には3次元のリストであっても、1次元のリストに変換されてしまうため、3次元リストを2次元リストにしたい場合には、reduce関数を使うと任意の次元をキープすることが出来ます。

レベル3

要素の出現回数をカウントする

# 最大値が10の要素を100個持つ、リストを作成
data = Enum.map(1..100, fn _ -> :rand.uniform(10) end) 

# mapを用いて集計
Enum.reduce(data, %{}, fn n, acc -> 
  if Map.has_key?(acc, n) do
    Map.put(acc, n, acc[n]+1)
  else
    Map.put(acc, n, 1)
  end
end)
|> IO.inspect()

# 実行するたびに結果は変わります
# %{
#   1 => 11,
#   2 => 7,
#   3 => 15,
#   4 => 10,
#   5 => 15,
#   6 => 10,
#   7 => 11,
#   8 => 8,
#   9 => 9,
#   10 => 4
# }

ついでに、map型に対してreduce関数を用いてカウントの合計値が100になるかを確認しておきます。

|> Enum.reduce(0, fn {_, v}, acc -> 
  acc + v
end)
|> IO.puts()
# 100

単語のindexを作成する

リストに含まれる単語に対してindex番号を割り振るための処理をreduce関数を用いて記述します。[A, B, C, A]というデータに対して、固有のインデックス番号(今回は整数値)を作成してA=1, B=2, C=3のようになります。重複は取り除きます。

# ランダムに取得する要素群をまとめたリスト
names = [:tanaka, :takahashi, :yamada, :takanashi, :satou, :suzuki]
# namesに含まれる要素をランダムに1つ取得する操作を100回繰り返してリストを作成
data = Enum.map(1..100, fn _ -> Enum.random(names) end)

# indexを作成
Enum.reduce(data, {0, %{}}, fn n, {count, map_} -> 
  if Map.has_key?(map_, n) do
    {count, map_}
  else
    {count+1, Map.put(map_, n, count+1)}
  end
end)
|> IO.inspect()
# {6, %{satou: 2, suzuki: 4, takahashi: 6, takanashi: 3, tanaka: 1, yamada: 5}}

keyを確認して、カウント値を用いて上書きを行なっているだけですが、今回のポイントとしてはアキュムレータータプルというデータ構造を用いて、2つの値を内包している点です。このようにタプルに複数の型の値を内包することで、多くの処理をreduce関数を用いて記述することが出来ます。

最後に

map, filter, reduceを組み合わせることで、ほぼ全ての繰り返し処理は関数型言語で表現可能になります。mapfilterと異なり、reduceElixirでは列挙型を任意の型の値に変換することが出来ます。つまりは、reduceを使う時、それは列挙型を別の型の値に変換したい時ということです。しかし、忘れてはいけないのは該当する処理の多くはすでにEnumの関数に実装されている場合が多いということです。

reduce関数を記述する前に、一度、Enumのドキュメントを覗いて、すでに同じ処理が実装されていないかを確認するクセをつけておくと、後から後悔する時間が減ります(経験者は語る)...

今回紹介した話の多くは「プログラミングElixir」から仕入れたものばかりです。reduceの詳細な解説はありませんが、関数型言語での様々な処理のパターンを学ぶことが出来るため、Elixirに興味がない方へもオススメの一冊です。

プログラミングElixir

プログラミングElixir

  • 作者:Dave Thomas
  • 発売日: 2016/08/19
  • メディア: 単行本(ソフトカバー)

参考文献