Elixir episode:3 Enumerable

# 環境

```shell-session:sh
$ lsb_release -d
Description:    Ubuntu 18.04.2 LTS

$ elixir -v
Erlang/OTP 21 [erts-10.3.5] [source] [64-bit] [smp:8:8] [ds:8:8:10] [async-threads:1] [hipe]

Elixir 1.8.2 (compiled with Erlang/OTP 20)
```

# はじめに

[Elixir episode:2 構造体](https://qiita.com/feelinguy/items/520f97cde87ce518095f) までの `fg` プロジェクトを使用する。
`Fg.List` に対する `Enumerable` プロトコルを実装する。

# プロトコルって何？

あっちとそっちで遣り取りするための取り決め（規約）。

私「`Fg.List` は数え上げられる(Enumerable)けどOK？」
Elixir「いや、規約に合わせて４つの関数を実装しておいて」
私「めんどくせー」

みたいな。

[Enumerable — Elixir vx.x.x](https://hexdocs.pm/elixir/Enumerable.html#content)

実装できると楽しい。

```elixir:iex
iex(1)> list = Fg.List.new([0, 1, 2])
%Fg.List{top: %Fg.Cell{fun: #Function<2.85842498/1 in Fg.Cell.new/2>}}
iex(2)> Enum.count(list)
3
iex(3)> Enum.member?(list, 3)
false
iex(4)> stream = Stream.cycle(list)
#Function<10.117072283/2 in Stream.cycle/1>    
iex(5)> Enum.slice(stream, 2, 5)
[2, 0, 1, 2, 0]
iex(6)> Enum.take(stream, 9)
[0, 1, 2, 0, 1, 2, 0, 1, 2]
iex(7)> Stream.map(stream, fn n -> n * 111 end) |>
...(7)> Enum.take(9)
[0, 111, 222, 0, 111, 222, 0, 111, 222]
```

`Enumerable` を実装するには、
畳み込み(fold/reduce)を理解していなければならない。

# `reduce/3` へ至る道のり

以下も参考にしてみてください。

- [flatten 関数が理解できなかった その１](https://qiita.com/feelinguy/items/43bfeebec63b63a51847)
- [flatten 関数が理解できなかった その２](https://qiita.com/feelinguy/items/9ccb26f7aaf1f3a6187e)

まずはリストを反転させることを考える。

```elixir:
defmodule Ex do
  def reverse([]), do: []
  def reverse([h | t]), do: reverse(t) ++ [h]
end
```

アキュムレータ（累算器）を導入する。

```elixir:
defmodule Ex do
  def reverse([], acc), do: acc
  def reverse([h | t], acc), do: reverse(t, [h | acc])
end
```

「リスト操作」を関数として抜き出し一般化する。

```elixir:
defmodule Ex do
  def reduce([], acc, _fun), do: acc
  def reduce([h | t], acc, fun), do: reduce(t, fun.(h, acc), fun)
end
```

一般的にこの `reduce/3` は左畳み込み(foldl)と呼ばれる。

## `foldl/3` `reverse/1` `append/2`

プロトコルを実装する前に下準備。
左畳み込みを Elixir の `List.foldl/3` に名前を合わせて実装し、
これを使って `reverse/1` `append/2` も実装する。

```elixir:fg/lib/fg/list.ex
defmodule Fg.List do
  alias __MODULE__, as: Me
  alias Fg.Cell
  ...
  # 追加
  def foldl(me = %Me{}, acc, fun) when is_function(fun, 2) do
    _foldl(me, acc, fun)
  end

  defp _foldl(%Me{top: %Cell{fun: nil}}, acc, _fun), do: acc

  defp _foldl(me, acc, fun) do
    _foldl(tail(me), fun.(head(me), acc), fun)
  end

  def reverse(me = %Me{}), do: foldl(me, new(), &cons/2)

  def append(me1 = %Me{}, me2 = %Me{}) do
    me1
    |> reverse()
    |> foldl(me2, &cons/2)
  end
end
```

# `Enumerable` を実装する

モジュール（構造体）が `Enumerable` であるためには、

1. `reduce/3`：畳み込み
2. `count/1`：要素数
3. `member?/2`：要素判定
4. `slice/1`：部分切り出し

を実装していなければならないが、
`reduce/3` の実装さえあれば他の３つはオプションにできる。
`reduce/3` は線形探索になるので、他の探索法が可能ならば残り３つを実装する。

先の `Ex.reduce/3` を `Enumerable` に表現するならば、

```elixir:
# 例えです。動きませんよ。
defimpl Enumerable, for: Ex do
  def reduce([], {:cont, acc}, _fun), do: {:done, acc}
  def reduce([h | t], {:cont, acc}, fun) do
    reduce(t, fun.(h, acc), fun)
  end

  def reduce(_list, {:halt, acc}, _fun), do: {:halted, acc}
  def reduce(list, {:suspend, acc}, fun) do
    {:suspended, acc, &reduce(list, &1, fun)}
  end
  ...
end
```

このように書き換えなければならない。
今回の場合 `reduce/3` の第１引数に `%Fg.List{}` を持ってくる。

いざ出陣。

```elixir:fg/lib/fg/list.ex
defmodule Fg.List do
  ...
end

# 追加
defimpl Enumerable, for: Fg.List do
  alias Fg.List, as: Me
  alias Fg.Cell

  # 終了する場合
  def reduce(%Me{top: %Cell{fun: nil}}, {:cont, acc}, _fun), do: {:done, acc}
  # 継続中
  def reduce(me = %Me{}, {:cont, acc}, fun) do
    reduce(Me.tail(me), fun.(Me.head(me), acc), fun)
  end

  # 中断する場合
  def reduce(%Me{}, {:halt, acc}, _fun), do: {:halted, acc}
  # 停止する場合
  def reduce(me = %Me{}, {:suspend, acc}, fun) do
    # 再開時のアキュムレータ、１引数関数を返す
    {:suspended, acc, &reduce(me, &1, fun)}
  end

  # Fg.List は片方向連結リスト（線形探索）なので reduce/3 に任せる
  def count(%Me{}), do: {:error, __MODULE__}  # 未定義という意味

  def member?(%Me{}, _value), do: {:error, __MODULE__}

  def slice(%Me{}), do: {:error, __MODULE__}
end
```

`{:suspended, acc, &reduce(struct, &1, fun)}` の意味がわかりづらいと思う。
`{:suspended, 再開時アキュムレータ, 再開時アキュムレータを受け取る関数}` である。
`&reduce(struct, &1, fun)` は `fn acc -> reduce(struct, acc, fun) end` と等価である。

処理が再開する場合に備えて、これまでのアキュムレータはもちろん、
そのアキュムレータを受け取る再開用関数も返す、という意味だ。

これにて `Fg.List` は `Enum` `Stream` が面倒を診てくれるようになった。

# `Collectable`

[Collectable — Elixir vx.x.x](https://hexdocs.pm/elixir/Collectable.html#content)

`Enumerable` の対局。他の `Enumerable` なものを取り込めるようにする。

```elixir:iex
iex(1)> Enum.into(1..3, [])
[1, 2, 3]
iex(2)> Enum.into(1..3, %MapSet{})
#MapSet<[1, 2, 3]>
iex(3)> Enum.into(1..3, MapSet.new([4,5,6]))
#MapSet<[1, 2, 3, 4, 5, 6]>
iex(4)> Enum.into(1..3, [4,5,6])
warning: the Collectable protocol is deprecated for non-empty lists. The behaviour of things like Enum.into/2 or "for" comprehensions with an :into option is incorrect when collecting into non-empty lists. If you're collecting into a non-empty keyword list, consider using Keyword.merge/2 instead. If you're collecting into a non-empty list, consider concatenating the two lists with the ++ operator.
  (elixir) lib/collectable.ex:83: Collectable.List.into/1
  (elixir) lib/enum.ex:1227: Enum.into_protocol/2
  (stdlib) erl_eval.erl:680: :erl_eval.do_apply/6
  (elixir) src/elixir.erl:258: :elixir.eval_forms/4
  (iex) lib/iex/evaluator.ex:257: IEx.Evaluator.handle_eval/5

[4, 5, 6, 1, 2, 3]
```

「空リストじゃないもんに `into` すんなよ」って怒られた。
なんでこれが非推奨なんだろ？
それは実装してみると分かります。

わざとシンプルに書いて間違えてみる。

```elixir:fg/lib/fg/list.ex
defmodule Fg.List do
  ...
end

# 追加
defimpl Collectable, for: Fg.List do
  alias Fg.List, as: Me

  def into(me = %Me{}) do
    collector = fn
       acc, {:cont, elem} -> Me.cons(elem, acc)
       acc,  :done        -> acc
      _acc,  :halt        -> :ok
    end

    {me, collector}  # {アキュムレータ初期値, ２引数関数}
  end
end
```
```elixir:iex
iex(1)> Enum.into(1..3, [4,5,6])
warning: ...
[4, 5, 6, 1, 2, 3]
iex(2)> Enum.into(1..3, Fg.List.new [4,5,6]) |> Enum.to_list()
[3, 2, 1, 4, 5, 6]
```

まるで違ったねぇ。
自分のケツに突っ込むんだね、こりゃー大変だ。

## 軽い尻を後で差し出す

```elixir:fg/lib/fg/list.ex
defmodule Fg.List do
  ...
end

# 変更
defimpl Collectable, for: Fg.List do
  alias Fg.List, as: Me

  def into(me = %Me{}) do
    collector = fn
      acc, :done ->
        rev = Me.reverse(acc)  # ③反転で戻して
        Me.append(me, rev)     # ④ケツにつなげる

      acc, {:cont, elem} ->
        Me.cons(elem, acc)     # ②それに貯めていくと逆順になるので

      _acc, :halt ->
        :ok
    end

    {Me.new(), collector}      # ①空リストを渡して
  end
end
```
```elixir:iex
iex(1)> Enum.into(1..3, [4,5,6])
warning: ...
[4, 5, 6, 1, 2, 3]
iex(2)> Enum.into(1..3, Fg.List.new [4,5,6]) |> Enum.to_list()
[4, 5, 6, 1, 2, 3]
```

④ `append/2` が非効率だね。
空リストに対して `into` ならば実質 `reverse` しか回らない。
`append` は単にアキュムレータを返却するだけで済むから。
素直に `[4,5,6] ++ (Enum.to_list 1..3)` にしてよってことだね。

もちろん `for` もいけるぜー。

```elixir:iex
iex(1)> codes = [12414, 12383, 12397, 12540, 12494, 12471]
[12414, 12383, 12397, 12540, 12494, 12471]
iex(2)> (for code <- codes, into: Fg.List.new(), do: <<code::utf8>>) |>
...(2)> Enum.join() |>
...(2)> IO.puts()
またねーノシ
:ok
```