Перечислимый протокол

Протокол перечислимого объекта, используемый модулями 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()

Результат операции сворачивания

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 определена в рекурсивной форме.

reducer()

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

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

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

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

result()

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

Результат операции сворачивания.

Он может быть выполнен, когда перечисление завершено, достигнув конца, или остановлен/приостановлен, когда перечисление было остановлено или приостановлено функцией 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)

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

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

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

member?(enumerable, element)

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

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

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

reduce(enumerable, acc, fun)

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

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

См. документацию по типам 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)

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

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

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

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

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

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