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

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

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

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

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

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

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

t()

t() :: term()

Функции

count(enumerable)

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

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

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

member?(enumerable, element)

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

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

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

reduce(enumerable, acc, fun)

Сокращает 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)

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

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

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

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

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

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