Qiita Teams that are logged in
You are not logged in to any team

Log in to Qiita Team
Community
OrganizationAdvent CalendarQiitadon (β)
Service
Qiita JobsQiita ZineQiita Blog
0
Help us understand the problem. What is going on with this article?
@feelinguy

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(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 の実装さえあれば他の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, :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
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
0
Help us understand the problem. What is going on with this article?
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.
Sign Up
If you already have a Qiita account Login
0
Help us understand the problem. What is going on with this article?