Help us understand the problem. What is going on with this article?

Elixir episode:3 Enumerable

環境

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 構造体 までの fg プロジェクトを使用する。
Fg.List に対する Enumerable プロトコルを実装する。

プロトコルって何?

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

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

みたいな。

Enumerable — Elixir vx.x.x

実装できると楽しい。

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 へ至る道のり

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

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

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

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

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

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

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 も実装する。

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(%Me{} = me1, %Me{} = me2) 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 の実装さえあれば他の3つはオプションにできる。
reduce/3 は線形探索になるので、他の探索法が可能ならば残り3つを実装する。

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

# 例えです。動きませんよ。
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 の第1引数に %Fg.List{} を持ってくる。

いざ出陣。

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
    # 再開時のアキュムレータ、1引数関数を返す
    {: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.ListEnum Stream が面倒を診てくれるようになった。

Collectable

Collectable — Elixir vx.x.x

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

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 すんなよ」って怒られた。
なんでこれが非推奨なんだろ?
それは実装してみると分かります。

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

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}  # {アキュムレータ初期値, 2引数関数}
  end
end
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]

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

軽い尻を後で差し出す

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 ->
        rev = Me.reverse(acc)  # ③反転で戻して
        Me.append(me, rev)     # ④ケツにつなげる

      _acc, :halt ->
        :ok
    end

    {Me.new(), collector}      # ①空リストを渡して
  end
end
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 もいけるぜー。

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
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした