環境
$ 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つの関数を実装しておいて」
私「めんどくせー」
みたいな。
実装できると楽しい。
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
も実装する。
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
であるためには、
-
reduce/3
:畳み込み -
count/1
:要素数 -
member?/2
:要素判定 -
slice/1
:部分切り出し
を実装していなければならないが、
reduce/3
の実装さえあれば他の3つはオプションにできる。
reduce/3
は線形探索になるので、他の探索法が可能ならば残り3つを実装する。
先の Ex.reduce/3
を Enumerable
に表現するならば、
# 例えです。動きませんよ。
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{}
を持ってくる。
いざ出陣。
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.List
は Enum
Stream
が面倒を診てくれるようになった。
Collectable
Enumerable
の対局。他の Enumerable
なものを取り込めるようにする。
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
すんなよ」って怒られた。
なんでこれが非推奨なんだろ?
それは実装してみると分かります。
わざとシンプルに書いて間違えてみる。
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(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]
まるで違ったねぇ。
自分のケツに突っ込むんだね、こりゃー大変だ。
軽い尻を後で差し出す
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
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(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