Протокол Enumerable protocol

Протокол Enumerable используется модулями Enum и Stream.

При вызове функции в модуле Enum, первый аргумент обычно представляет собой коллекцию, которая должна реализовывать этот протокол. Например, выражение:

Enum.map([1, 2, 3], &(&1 * 2))

вызывает Enumerable.reduce/3 для выполнения операции сведения, которая создаёт отображённый список, вызывая функцию отображения &(&1 * 2) для каждого элемента в коллекции и потребляя элемент с накопленным списком.

Внутренне, Enum.map/2 реализуется следующим образом:

def map(enumerable, fun) do
  reducer = fn x, acc -> {:cont, [fun.(x) | acc]} end
  Enumerable.reduce(enumerable, {:cont, []}, reducer) |> elem(1) |> :lists.reverse()
end

Обратите внимание, что пользовательская функция обернута в функцию reducer/0. Функция reducer/0 должна возвращать помеченное кортеж после каждого шага, как описано в типе acc/0. В конце, Enumerable.reduce/3 возвращает result/0.

Этот протокол использует помеченные кортежи для обмена информацией между функцией редуктора и типом данных, реализующим протокол. Это позволяет эффективно перечислять ресурсы, такие как файлы, гарантируя при этом, что ресурс будет закрыт в конце перечисления. Этот протокол также позволяет приостанавливать перечисление, что полезно при необходимости интерлирования между многими перечисляемыми объектами (например, в функции zip).

Для реализации этого протокола необходимо четыре функции: reduce/3, count/1, member?/2 и slice/1. Ядром протокола является функция reduce/3. Все остальные функции являются оптимизированными путями для структур данных, которые могут реализовать определённые свойства лучше, чем за линейное время.

Краткое описание

Типы

acc()

Значение аккумулятора на каждом шаге

continuation()

Частично применённая функция reduce

reducer()

Функция редуктора

result()

Результат операции reduce

slicing_fun()

Функция среза, которая получает начальную позицию и количество элементов в срезе

t()

Функции

count(enumerable)

Возвращает количество элементов в перечисляемом объекте

member?(enumerable, element)

Проверяет, существует ли элемент в перечисляемом объекте

reduce(enumerable, acc, fun)

Сводит перечисляемый объект к элементу

slice(enumerable)

Возвращает функцию, которая осуществляет срез данных непрерывно

Типы

acc()

acc() :: {:cont, term()} | {:halt, term()} | {:suspend, term()}

Значение аккумулятора на каждом шаге.

Он должен быть помеченным кортежем с одним из следующих «тегов»:

• :cont - перечисление должно продолжить работу
• :halt - перечисление должно быть немедленно остановлено
• :suspend - перечисление должно быть немедленно приостановлено

В зависимости от значения аккумулятора, возвращаемый Enumerable.reduce/3 результат будет меняться. Дополнительную информацию можно найти в документации типа result/0.

Если функция reducer/0 возвращает :suspend аккумулятор, вызывающий код должен явно обработать его и никогда не должен его раскрывать.

continuation()

continuation() :: (acc() -> result())

Частично применённая функция reduce.

Продолжение — это замыкание, возвращаемое в результате, когда перечисление приостанавливается. При вызове оно ожидает новый аккумулятор и возвращает результат.

Продолжение можно тривиально реализовать, если функция reduce определена в рекурсивной форме. Если функция рекурсивна, всё состояние передаётся в качестве аргументов, поэтому продолжение — это частично применённая функция reduce.

reducer()

reducer() :: (term(), term() -> acc())

Функция редуктора.

Должна вызываться с элементом перечисляемого объекта и содержимым аккумулятора.

Возвращает аккумулятор для следующего шага перечисления.

result()

result() ::
  {:done, term()} | {:halted, term()} | {:suspended, term(), continuation()}

Результат операции reduce.

Он может быть выполнен, когда перечисление завершено, достигнув своего конца, или остановлен/приостановлен, когда перечисление было остановлено или приостановлено функцией reducer/0.

Если функция reducer/0 возвращает :suspend аккумулятор, кортеж :suspended должен быть явно обработан вызывающим кодом и никогда не должен раскрываться. На практике это означает, что обычные функции перечисления должны заботиться только о :done и :halted результатах.

Кроме того, вызов :suspend всегда должен быть после другим вызовом, в конечном счёте останавливая или продолжая до конца.

slicing_fun()

slicing_fun() ::
  (start :: non_neg_integer(), length :: pos_integer() -> [term()])

Функция среза, которая получает начальную позицию и количество элементов в срезе.

Позиция start — это число >= 0 и гарантируется, что она существует в перечисляемом объекте. Длина — это число >= 1 таким образом, что start + length <= count, где count — максимальное количество элементов в перечисляемом объекте.

Функция должна возвращать список, не пустой, в котором количество элементов равно length.

t()

t() :: term()

Функции

count(enumerable)

count(t()) :: {:ok, non_neg_integer()} | {:error, module()}

Возвращает количество элементов в перечисляемом объекте.

Если вы можете посчитать количество элементов в перечисляемом объекте, оно должно возвращать {:ok, count}.

В противном случае оно должно возвращать {:error, __MODULE__} и будет использован алгоритм по умолчанию, основанный на reduce/3, который выполняется за линейное время.

member?(enumerable, element)

member?(t(), term()) :: {:ok, boolean()} | {:error, module()}

Проверяет, существует ли элемент в перечисляемом объекте.

Если вы можете проверить членство данного элемента в перечисляемом объекте с === без прохода по всему перечисляемому объекту, оно должно возвращать {:ok, boolean}.

В противном случае оно должно возвращать {:error, __MODULE__} и будет использован алгоритм по умолчанию, основанный на reduce/3, который выполняется за линейное время.

reduce(enumerable, acc, fun)

reduce(t(), acc(), reducer()) :: result()

Сводит перечисляемый объект к элементу.

Большинство операций в Enum реализованы с использованием reduce. Эта функция должна применять заданную функцию reducer/0 к каждому элементу перечисляемого объекта и действовать в соответствии с ожидаемым аккумулятором.

См. документацию типов result/0 и acc/0 для получения дополнительной информации.

Примеры

В качестве примера, вот реализация reduce для списков:

def reduce(_,       {:halt, acc}, _fun),   do: {:halted, acc}
def reduce(list,    {:suspend, acc}, fun), do: {:suspended, acc, &reduce(list, &1, fun)}
def reduce([],      {:cont, acc}, _fun),   do: {:done, acc}
def reduce([h | t], {:cont, acc}, fun),    do: reduce(t, fun.(h, acc), fun)

slice(enumerable)

slice(t()) ::
  {:ok, size :: non_neg_integer(), slicing_fun()} | {:error, module()}

Возвращает функцию, которая осуществляет срез данных непрерывно.

Если перечисляемый объект имеет известную границу и может получить доступ к позиции в перечисляемом объекте без перехода через все предыдущие элементы, оно должно возвращать {:ok, size, slicing_fun}.

В противном случае оно должно возвращать {:error, __MODULE__} и будет использован алгоритм по умолчанию, основанный на reduce/3, который выполняется за линейное время.

Отличия от count/1

Значение size , возвращаемое этой функцией, используется для проверок границ, поэтому крайне важно, что эта функция возвращает :ok только в том случае, если получение size перечисляемого объекта является дешёвым, быстрым и занимает постоянное время. В противном случае самые простые операции, такие как Enum.at(enumerable, 0), станут слишком дорогими.

С другой стороны, функция count/1 в этом протоколе должна быть реализована всякий раз, когда вы можете посчитать количество элементов в коллекции.