elixirプロトコルについて(Enumerable)

elixir

elixirでは標準でいくつかのプロトコルを提供しているが、あまり目立っていない。そこで、モジュールではなくプロトコルに着目して調べてみた。

Enumerable

Enumerableとは、「数え上げることができる」という意味で、主にEnum、StreamモジュールがEnumerableを対象とした操作を行っている。

Enumerableが実装を要求する関数は、count/1, member?/2, reduce/3の3個で、
それらを実装したモジュールはEnumerableになり、Enum, Streamモジュール
の恩恵をうけることができる。

とりあえず、フィボナッチ数を生成するモジュールFibを作ってみる。

まず、構造体と初期化子を作ります。これはプロトコルでは要請されていないが、お約束という事で。デフォルトでは無限に生成するようcountは:infinityにしてみる。

defmodule Fib do
  defstruct f0: 1, f1: 1, count: :infinity
  def new() do
    %Fib{}
  end
  def new(count) do
    %Fib{count: count}
  end
end

次に、Enumerableを実装するが、以下の3つの関数の
実装が求められている。

   def count(collection) :: {:ok, non_neg_integer} | {:error, module}
   def member?(collection, value) :: {:ok, boolean} | {:error, module}
   def reduce(collection, acc, fun) :: {:done, term} |
                                       {:halted, term} |
                                       {:suspended, term, continuation}

このうち、count/1, member?/2はデフォルトの実装が提供されていて、デフォ
ルトの実装を使う場合、{:error, module}を返すとよい。デフォルトの実装は、
reduce/3を使い、線形時間がかかるので、データ構造上、それよりも高速に求
められることがわかっている場合にのみ、カスタム実装を行うべき。

例えば、フィボナッチ数列のcountは、:infinityでない場合なら、
構造体のフィールドから直接求めることが可能。:infinityの
場合はデフォルト実装にお任せするようにする。

   def count(%Fib{count: :infinity}), do: {:error, __MODULE__}
   def count(fib), do: {:ok, fib.count}

一方、member?/2は、結局１つひとつ比較するしかないので、デフォルト実装にお任せ。

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

残りはreduce/3だが、アキュムレータにタグが付けられていることに注意して実装する。

  • :cont - 数え上げを継続します。 {:cont, acc}か{:done, acc}を返します。
  • :halt - 直ちに数え上げを停止します。 {:halted, acc}を返します。
  • :suspend - 直ちに数え上げをサスペンドします。 {:suspended, acc, fn(x) -> reduce(enum, x, fun) end}を返します。
   def reduce(e, acc, fun) do
     reduce(e.f0, e.f1, e.count, acc, fun)
   end
   def reduce(_f0, _f1, 0, {:cont, acc}, _fun) do
     {:done, acc}
   end
   def reduce(f0, f1, n, {:cont, acc}, fun) do
     reduce(f1, f0 + f1, n-1, fun.(f0, acc), fun)
   end
   def reduce(_, _, _, {:halt, acc}, _fun) do
     {:halted, acc}
   end
   def reduce(f0, f1, n, {:suspend, acc}, fun) do
     {:suspended, acc, &reduce(f0, f1, n, &1, fun)}
   end

このように、reduceではフィボナッチ数を計算しながらカウントが0になったら`{:done, acc}`を返すことになる。
そしてナイスなことに、この状態でStreamにも対応出来ている。

さてさっそく、使ってみる。お題として、10から100までのフィボナッチ数列の、最初の二つを出力するというものにしてみる。

iex(1)> import_file ("codes/protocol_fib.exs")
{:module, Enumerable.Fib,
 <<70, 79, 82, 49, 0, 0, 14, 120, 66, 69, 65, 77, 69, 120, 68, 99, 0, 0, 1, 173, 131, 104, 2, 100, 0, 14, 101, 108, 105, 120, 105, 114, 95, 100, 111, 99, 115, 95, 118, 49, 108, 0, 0, 0, 2, 104, 2, ...>>,
 {:__impl__, 1}}
iex(2)> Fib.new |> Stream.filter(&Enum.member?(10..100, &1)) |>
...(2)> Stream.take(2) |> Enum.to_list
[13, 21]
iex(3)>

Fib.newとして、無限数列としているにも拘わらず、きちんと計算されて
いるのは、Streamのお陰。Enumerableプロトコルを実装するだけで遅延評価の恩恵を受けられるのは素晴しい。