Elixir v1.0.5 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 underneath 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 cons’ing 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 given function is wrapped into a reducer
function.
The reducer
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 function to communicate to the underlying enumerable the end of enumeration, allowing any open resource 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
The accumulator value for each step
A partially applied reduce function
The reducer function
The result of the reduce operation
Functions
Retrieves the collection’s size
Checks if a value exists within the collection
Reduces the collection into a value
Types
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
type docs for more information.
In case a reducer function returns a :suspend
accumulator,
it must be explicitly handled by the caller and never leak.
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 :: (term, term -> acc)
The reducer function.
Should be called with the collection element and the accumulator contents. Returns the accumulator for the next enumeration step.
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 function.
In case a reducer 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 :: term
Functions
Specs
count(t) :: {:ok, non_neg_integer} | {:error, module}
Retrieves the collection’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.
Specs
member?(t, term) ::
{:ok, boolean} |
{:error, module}
Checks if a value exists within the collection.
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.
Reduces the collection into a value.
Most of the operations in Enum
are implemented in terms of reduce.
This function should apply the given reducer
function to each
item in the collection 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)