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()

Specs

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

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

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

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

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

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

continuation()

Specs

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

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

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

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

reducer()

Specs

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

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

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

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

result()

Specs

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

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

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

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

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

slicing_fun()

Specs

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

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

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

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

t()

Specs

t() :: term()

Функции

count(перечисляемый)

Характеристики

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

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

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

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

member?(перечисляемый, элемент)

Характеристики

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

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

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

reduce(перечисляемый, acc, fun)

Характеристики

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(перечисляемый)

Характеристики

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()

Specs

continuation()

Specs

reducer()

Specs

result()

Specs

slicing_fun()

Specs

t()

Specs

Функции

count(перечисляемый)

Характеристики

member?(перечисляемый, элемент)

Характеристики

reduce(перечисляемый, acc, fun)

Характеристики

Примеры

slice(перечисляемый)

Характеристики

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

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