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

The accumulator value for each step.

It must be a tagged tuple with one of the following "tags":

• :cont - the enumeration should continue
• :halt - the enumeration should halt immediately
• :suspend - the enumeration should be suspended immediately

Depending on the accumulator value, the result returned by Enumerable.reduce/3 will change. Please check the result/0 type documentation for more information.

In case a reducer/0 function returns a :suspend accumulator, it must be explicitly handled by the caller and never leak.

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

A partially applied reduce function.

The continuation is the closure returned as a result when the enumeration is suspended. When invoked, it expects a new accumulator and it returns the result.

A continuation can be trivially implemented as long as the reduce function is defined in a tail recursive fashion. If the function is tail recursive, all the state is passed as arguments, so the continuation is the reducing function partially applied.

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

The reducer function.

Should be called with the enumerable element and the accumulator contents.

Returns the accumulator for the next enumeration step.

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

The result of the reduce operation.

It may be done when the enumeration is finished by reaching its end, or halted/suspended when the enumeration was halted or suspended by the tagged accumulator.

In case the tagged :halt accumulator is given, the :halted tuple with the accumulator must be returned. Functions like Enum.take_while/2 use :halt underneath and can be used to test halting enumerables.

In case the tagged :suspend accumulator is given, the caller must return the :suspended tuple with the accumulator and a continuation. The caller is then responsible of managing the continuation and the caller must always call the continuation, eventually halting or continuing until the end. Enum.zip/2 uses suspension, so it can be used to test whether your implementation handles suspension correctly. You can also use Stream.zip/2 with Enum.take_while/2 to test the combination of :suspend with :halt.

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

A slicing function that receives the initial position, the number of elements in the slice, and the step.

The start position is a number >= 0 and guaranteed to exist in the enumerable. The length is a number >= 1 in a way that start + length * step <= count, where count is the maximum amount of elements in the enumerable.

The function should return a non empty list where the amount of elements is equal to length.

@type t() :: term()

All the types that implement this protocol.

@type t(_element) :: t()

An enumerable of elements of type element.

This type is equivalent to t/0 but is especially useful for documentation.

For example, imagine you define a function that expects an enumerable of integers and returns an enumerable of strings:

@spec integers_to_strings(Enumerable.t(integer())) :: Enumerable.t(String.t())
def integers_to_strings(integers) do
  Stream.map(integers, &Integer.to_string/1)
end

@type to_list_fun() :: (t() -> [term()])

Receives an enumerable and returns a list.

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

Retrieves the number of elements in the enumerable.

It should return {:ok, count} if you can count the number of elements in enumerable in a faster way than fully traversing it.

Otherwise it should return {:error, __MODULE__} and a default algorithm built on top of reduce/3 that runs in linear time will be used.

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

Checks if an element exists within the enumerable.

It should return {:ok, boolean} if you can check the membership of a given element in enumerable with ===/2 without traversing the whole of it.

Otherwise it should return {:error, __MODULE__} and a default algorithm built on top of reduce/3 that runs in linear time will be used.

When called outside guards, the in and not in operators work by using this function.

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

Reduces the enumerable into an element.

Most of the operations in Enum are implemented in terms of reduce. This function should apply the given reducer/0 function to each element in the enumerable and proceed as expected by the returned accumulator.

See the documentation of the types result/0 and acc/0 for more information.

Examples

As an example, here is the implementation of reduce for lists:

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)

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

Returns a function that slices the data structure contiguously.

It should return either:

• {:ok, size, slicing_fun} - if the enumerable has a known bound and can access a position in the enumerable without traversing all previous elements. The slicing_fun will receive a start position, the amount of elements to fetch, and a step.

• {:ok, size, to_list_fun} - if the enumerable has a known bound and can access a position in the enumerable by first converting it to a list via to_list_fun.

• {:error, __MODULE__} - the enumerable cannot be sliced efficiently and a default algorithm built on top of reduce/3 that runs in linear time will be used.

Differences to count/1

The size value returned by this function is used for boundary checks, therefore it is extremely important that this function only returns :ok if retrieving the size of the enumerable is cheap, fast, and takes constant time. Otherwise the simplest of operations, such as Enum.at(enumerable, 0), will become too expensive.

On the other hand, the count/1 function in this protocol should be implemented whenever you can count the number of elements in the collection without traversing it.