Enumerable протокол

Протокол 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/1 и zip/2).

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

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

Типы

acc(): Значение накопителя на каждом шаге.
continuation(): Частично применённая функция reduce.
reducer(): Функция редукции.
result(): Результат операции reduce.
slicing_fun(): Функция разбиения, которая получает начальную позицию и количество элементов в разбиении.
t()

Функции

count(enumerable): Возвращает количество элементов в enumerable.
member?(enumerable, element): Проверяет, существует ли element в enumerable.
reduce(enumerable, acc, fun): Применяет редукцию к enumerable в элемент.
slice(enumerable): Возвращает функцию, которая разбиения структуру данных по непрерывным участкам.

Типы

acc()Источник

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

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

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

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

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

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

continuation()Источник

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

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

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

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

reducer()Источник

@type reducer() :: (element :: term(), current_acc :: acc() -> updated_acc :: acc())

Функция редукции.

Должна вызываться с элементом enumerable и содержимым накопителя.

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

result()Источник

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

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

Может быть завершённым, когда перечисление завершено, или остановленным/приостановленным, когда перечисление было остановлено или приостановлено помеченным накопителем.

В случае, если помеченный :halt накопитель, :halted кортеж с накопителем должен быть возвращён. Функции, такие как Enum.take_while/2, используют :halt внизу и могут использоваться для проверки останавливаемых перечисляемых объектов.

В случае, если помеченный :suspend накопитель, :suspended кортеж с накопителем и продолжением должен быть возвращён. Вызывающая сторона затем несёт ответственность за управление продолжением и должна всегда вызывать продолжение, в конечном итоге останавливая или продолжая, пока не достигнет конца. Enum.zip/2 использует приостановку, поэтому она может использоваться для проверки того, правильно ли ваша реализация обрабатывает приостановку. Вы также можете использовать Stream.zip/2 с Enum.take_while/2, чтобы проверить комбинацию :suspend с :halt.

slicing_fun()Источник

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

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

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

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

t()Источник

@type t() :: term()

END_OF_DOCUMENT_MARKER

Функции

count(enumerable)Source

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

Возвращает количество элементов в enumerable.

Должно вернуть {:ok, count} если вы можете посчитать количество элементов в enumerable без его обхода.

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

member?(enumerable, element)Source

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

Проверяет, существует ли element в enumerable.

Должно вернуть {:ok, boolean} если вы можете проверить принадлежность данного элемента к enumerable с помощью ===/2 без обхода всего enumerable.

Когда вызывается вне охранных условий, операторы in и not in работают, используя эту функцию.

reduce(enumerable, acc, fun)Source

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

Приводит enumerable к элементу.

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

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

Примеры

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

def reduce(_list, {: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([head | tail], {:cont, acc}, fun), do: reduce(tail, fun.(head, acc), fun)

slice(enumerable)Source

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

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

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

Различия с `count/1`

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

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

Настройки Enumerable протокол

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

Типы

Функции

Типы

acc()Источник

continuation()Источник

reducer()Источник

result()Источник

slicing_fun()Источник

t()Источник

Функции

count(enumerable)Source

member?(enumerable, element)Source

reduce(enumerable, acc, fun)Source

Примеры

slice(enumerable)Source

Различия с count/1

Enumerable протокол

Различия с `count/1`