作って学ぶEnumモジュール2、reduceとsum, max, min, filter

[作って学ぶEnumモジュール1、mapとto_list](https://qiita.com/pojiro/items/8865ccbde8a62174e52e)の続編として、
今回はreduceを作ってみたいと思います。

# MyEnum.reduce/3

reduceはreduce/2とreduce/3がありますが、reduce/3から作ってみます。
※reduce/3から作る理由は後述します。

まず仕様を確認します。

~~~elixir
iex(1)> h Enum.reduce/3
 
                        def reduce(enumerable, acc, fun)                        

  @spec reduce(t(), any(), (element(), any() -> any())) :: any()

Invokes fun for each element in the enumerable with the accumulator.

The initial value of the accumulator is acc. The function is invoked for each
element in the enumerable with the accumulator. The result returned by the
function is used as the accumulator for the next iteration. The function
returns the last accumulator.

## Examples

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

## Reduce as a building block

# ここは略、ただ、衝撃の一行だけ抜粋します。ワオ
Almost all of the functions in the Enum module can be implemented
on top of reduce. 
~~~

ざっくり読むと以下でしょうか。

- def reduce(enumerable, acc, fun)となっているので、第一引数は数え上げができるもの、第二引数はacc(?)、第三引数は関数
    - accumulator（累算器、積算器と訳されるようです）の初期値がacc
    - funはenumerableの各要素にaccとともに適用される、つまりfunは引数にelementとaccをとる
    - funの適用結果、fun.(element, acc)は次のiterationでaccとして使われる
    - reduceは最後のaccumulatorの値を返す
- enumerableに[1,2,3], funにfn x, acc -> x + acc endが与えられたら6を返す

理解するために、
Enum.reduce([1, 2, 3], 0, fn x, acc -> x + acc end)の、一度処理を追ってみます。

- 第一要素の処理は、fun.(1, 0) -> (1 + 0), これは次回のacc
- 第二要素の処理は、fun.(2, 1 + 0) -> (2 + (1 + 0)), これは次回のacc
- 第三要素の処理は、fun.(3, 2 + (1 + 0)) -> (3 + (2 + (1 + 0))), これがreduceの返り値

※作る途中でわからなくなったらここに戻って再確認しましょう。

ガワから書いてみます。

~~~my_enum.ex
defmodule MyEnum do
  def reduce(list, acc_init, func) do
  end
end
~~~

第一要素に関数を適用するとこうかな。

~~~my_enum.ex
defmodule MyEnum do
  def reduce([h|t], acc_init, func) do
    func.(h, acc_init)
  end
end
~~~

で、この値が次回のaccになるから。

~~~my_enum.ex
defmodule MyEnum do
  def reduce([h|t], acc_init, func) do
    reduce(, func.(h, acc_init), func)
  end
end
~~~

残りの配列tを処理したいです。

~~~my_enum.ex
defmodule MyEnum do
  def reduce([h|t], acc_init, func) do
    reduce(t, func.(h, acc_init), func)
  end
end
~~~

なんとなく書いたけど、これは果たしてreduceでしょうか。
一度立ち止まって、[1, 2, 3]で処理を追ってみてください。
。
。
。
。
。
。
。
。
空のリストの処理を忘れてました。再帰には終了条件が必要でした。

~~~my_enum.ex
defmodule MyEnum do
  def reduce([], acc_init, _func), do: acc_init # funcは使わないから_を接頭辞につけました。
  def reduce([h|t], acc_init, func)
    reduce(t, func.(h, acc_init), func))
  end
end
~~~

できた！確認しましょう。

~~~elixir
iex(1)> c "my_enum.ex"
[MyEnum]
iex(2)>  MyEnum.reduce([1,2,3], 0, fn x, acc -> x + acc end)
6 # ばっちり
iex(3)> MyEnum.reduce([1,2,3], 10, fn x, acc -> x + acc end)
16 # accの初期値を変えてもオッケー
~~~

MyEnumモジュールを[前回](https://qiita.com/pojiro/items/8865ccbde8a62174e52e)のコードを含めて見てみましょう。

~~~my_enum.ex
def module MyEnum do
  def map([], _func), do: []
  def map([h|t], func), do: [func.(h)|map(t, func)]
  def map(s..e, func), do: map(to_list(s..e), func)

  # 再帰だとacc_initの命名がいまいちなのでとりました。いつでも初期値ではないので。
  def reduce([], acc, _func), do: acc
  def reduce([h|t], acc, func), do: reduce(t, func.(h, acc), func)
  def reduce(s..e, acc, func), do: reduce(to_list(s..e), acc, func) # レンジを受けられるように追加

  def to_list(e..e), do: [e]
  def to_list(s..e) when s < e, do: [s| to_list((s+1)..e)]
  def to_list(s..e) when s > e, do: [s| to_list((s-1)..e)]

  def reverse(s..e), do: to_list(e..s)
end
~~~

次はとばしたreduce/2を作ります。

# MyEnum.reduce/2

まず、仕様を確認します。

~~~elixir
iex(1)> h Enum.reduce/2

                          def reduce(enumerable, fun)                           

  @spec reduce(t(), (element(), acc() -> acc())) :: acc()

Invokes fun for each element in the enumerable with the accumulator.

Raises Enum.EmptyError if enumerable is empty.

The first element of the enumerable is used as the initial value of the
accumulator. Then the function is invoked with the next element and the
accumulator. The result returned by the function is used as the accumulator for
the next iteration, recursively. When the enumerable is done, the last
accumulator is returned.

Since # 以下略、ここは各自読みましょう。 
~~~

ざっくり読むと以下でしょうか。はじめの二項がreduce/3と違います。

- def reduce(enumerable, fun)となっているので、第一引数は数え上げができるもの、第二引数は関数
- enumarableの第一要素がaccとして使われ、funはenumerableの次の要素とacc（第一要素）とともに適用される
- funの適用結果、fun.(element, acc)は次のiterationでaccとして使われる
- reduceは最後のaccumulatorの値を返す

これはエイヤで書いてみましょう。
。
。
。
。
。
。
。
。

~~~my_enum.ex
  def reduce([h|t], func), do: reduce(t, h, func)
  def reduce(s..e, func), do: reduce(to_list(s..e), func)
~~~

listの第一要素をaccとしてreduce/3を呼び出しています。これだけです。


reduce/3はありきで、よく使うパターン（enumerableの第一要素をaccとする）を
reduce/2として作ったのだろうと思います。

さて、reduceが手に入りました。
reduceを作る際に[1,2,3]を足し合わせて6を得るで動作確認していました。これってEnum.sumでは？

# MyEnum.sum/1

~~~my_enum.ex
  def sum(enumerable), do: reduce(enumerable, fn x, acc -> x + acc end)
~~~

これ以外にもリストに関数を適用して一つの値にするパターンってありますね。

- [1,2,3] -> 3, これができればmax
- [1,2,3] -> 1, これができればmin

# MyEnum.max/1, min/1

~~~my_enum.ex
  def max(enumerable) do
    reduce(enumerable,
      fn x, acc -> 
        cond do
          x > acc -> x # minは不等号の向きが逆なだけ
          true -> acc
        end
      end
    )
  end
~~~

「最大/最小」をaccに残すのがminとmaxでした。
ある「条件」に合致する要素を残すことができればfilterが作れそうです。

# MyEnum.filter/2

~~~my_enum.ex
  def filter(enumerable, func) do
    reduce(enumerable, [],
      fn x, acc -> 
        cond do
          func.(x) -> [x|acc]
          true -> acc
        end
      end
    )
    |> Enum.reverse # ここだけズル、リストを引数とするreverseを作ってないからです。
  end
~~~

イエイ！簡単ですね。でも、ちょっと疲れてきたので、ここまでとします:sweat_smile:

# まとめ

- Enumモジュールのreduce関数を仕様を調べて作ってみました。
- reduceを使うと、sum, max, filterがぱっと作れてしまうことをみました。
    - ※ h Enum.reduce/3にはmapがreduceを使ってmapも作れることが書いてありました。

reduceってすごいパワフルですね。

プログラムあるあるなのだろうと思いますが、
本質的な機能を作ることができると、その応用で容易にいろいろな機能が作ることができるいい例だと思いました。

reduceのような本質的な機能を作ることができる思考法を手に入れたいです。

~~作って学ぶEnumモジュールはこれで終わろうと思いますが、~~
Enumには他にも関数があるので、それらを作ってみるのはとてもいいドリルになりそうです:yum:

次回は[作って学ぶEnumモジュール3、Enumモジュールのオレオレ実装](https://qiita.com/pojiro/items/6d880829ea36c85856bf)です。

では、また！

**「いいね」よろしくお願いします！**:wink: