Enumerable

The Enumerable protocol is the basis of all the functions in the Enum module. Any type implementing it can be used as a collection argument to Enum functions.

We’re going to implement Enumerable for our Midi structure, so we’ll need to wrap the implementation in something like this:

defimpl Enumerable, for: Midi do 
  # ...
end

Major functions

The protocol is defined in terms of four functions: count, member?, reduce, and slice, as shown below:

defprotocol Enumerable do
  def count(collection)
  def member?(collection, value) 
  def reduce(collection, acc, fun) 
  def slice(collection)
end

The count function returns the number of elements in the collection. The member? function is truthy if the collection contains value. The reduce function applies the given function to successive values in the collection and the accumulator; the value it reduces becomes the next accumulator. Finally, slice is used to create a subset of a collection. Perhaps surprisingly, all the Enum functions can be defined in terms of these four.

However, it isn’t that simple. Maybe we’re using Enum.find to find a value in a large collection. Once we’ve found it, we want to halt the iteration because continuing is pointless. Similarly, we may want to suspend an iteration and resume it sometime later. These two features become particularly important when we talk about streams, which let us enumerate a collection lazily.

The reduce function

We’ll start with the most difficult function to implement, which is Enumerable.reduce. It’s worth reading the documentation for it before we start:

iex> h Enumerable.reduce
    def reduce(enumerable, acc, fun)
    @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 t:reducer/0 function to each item in the
enumerable and proceed as expected by the returned accumulator.
See the documentation of the types t:result/0 and t:acc/0 for more information.

## Examples

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)

The first two function heads do housekeeping: they handle the cases where the enumeration has been halted or suspended. Here are the versions for our MIDI enumerator:

def _reduce(_content, {:halt, acc}, _fun) do 
  {:halted, acc}
end
def _reduce(content, {:suspend, acc}, fun) do 
  {:suspended, acc, &_reduce(content, &1, fun)}
end

The next two function heads do the actual iteration. In the list example in the documentation, we see the typical pattern: check for the end condition ([ ]) and the recursive step [h|t].

We’ll do the same with our MIDI file, but we’ll use binaries instead of doing list pattern matching:

  def _reduce(_content = "", {:cont, acc}, _fun) do
    {:done, acc}
  end

  def _reduce(<<
                  type::binary-4,
                length::integer-32,
                  data::binary-size(length),
                  rest::binary
              >>,
              {:cont, acc},
              fun
             ) do
    frame = %Midi.Frame{type: type, length: length, data: data}
    _reduce(rest, fun.(frame, acc), fun)
  end

See how we split out the binary content of a frame, then wrap it into a Midi.Frame struct before passing it back. This means that folks who use our MIDI module will only see these frame structures and not the raw data.

Before we try this, there’s one little tweak we have to make. It might be noticeable that all our functions were named _reduce with a leading underscore. That’s because they need to work on the content of the MIDI file and not on the structure that wraps that content. We have a single function head that implements the actual reduce function, and that then forwards the call on to _reduce:

def reduce(%Midi{content: content}, state, fun) do 
  _reduce(content, state, fun)
end

At this point, we have enough code to try it out. We’ve included a MIDI file in the code/protocols directory for us to experiment with (courtesy of midiworld.com).