Enumerable protocol

Enumerable protocol used by Enum and Stream modules.

When you invoke a function in the Enum module, the first argument is usually a collection that must implement this protocol. For example, the expression:

Enum.map([1, 2, 3], &(&1 * 2))

invokes Enumerable.reduce/3 to perform the reducing operation that builds a mapped list by calling the mapping function &(&1 * 2) on every element in the collection and consuming the element with an accumulated list.

Internally, Enum.map/2 is implemented as follows:

def map(enum, fun) do
  reducer = fn x, acc -> {:cont, [fun.(x) | acc]} end
  Enumerable.reduce(enum, {:cont, []}, reducer) |> elem(1) |> :lists.reverse()
end

Notice the user-supplied function is wrapped into a reducer/0 function. The reducer/0 function must return a tagged tuple after each step, as described in the acc/0 type.

The reason the accumulator requires a tagged tuple is to allow the reducer/0 function to communicate the end of enumeration to the underlying enumerable, allowing any open resources to be properly closed. It also allows suspension of the enumeration, which is useful when interleaving between many enumerables is required (as in zip).

Finally, Enumerable.reduce/3 will return another tagged tuple, as represented by the result/0 type.

Summary

Types

acc()

The accumulator value for each step

continuation()

A partially applied reduce function

reducer()

The reducer function

result()

The result of the reduce operation

t()

Functions

count(enumerable)

Retrieves the enumerable’s size

member?(enumerable, element)

Checks if an element exists within the enumerable

reduce(enumerable, acc, fun)

Reduces the enumerable into an element

Types

acc()

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.

continuation()

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 is easily 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 would simply be the reducing function partially applied.

reducer()

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

The reducer function.

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

Returns the accumulator for the next enumeration step.

result()

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 reducer/0 function.

In case a reducer/0 function returns the :suspend accumulator, the :suspended tuple must be explicitly handled by the caller and never leak. In practice, this means regular enumeration functions just need to be concerned about :done and :halted results.

Furthermore, a :suspend call must always be followed by another call, eventually halting or continuing until the end.

t()

t() :: term

Functions

count(enumerable)

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

Retrieves the enumerable’s size.

It should return {:ok, size}.

If {:error, __MODULE__} is returned a default algorithm using reduce and the match (===) operator is used. This algorithm runs in linear time.

Please force use of the default algorithm unless you can implement an algorithm that is significantly faster.

member?(enumerable, element)

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

Checks if an element exists within the enumerable.

It should return {:ok, boolean}.

If {:error, __MODULE__} is returned a default algorithm using reduce and the match (===) operator is used. This algorithm runs in linear time.

Please force use of the default algorithm unless you can implement an algorithm that is significantly faster.

reduce(enumerable, acc, fun)

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 item in the enumerable and proceed as expected by the returned accumulator.

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

def reduce(_,       {: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([h | t], {:cont, acc}, fun),    do: reduce(t, fun.(h, acc), fun)