Enum.reduce Patterns in Elixir

In this week’s post I want to take a look at the Enum.reduce function. The documentation can explain the basics of how reduce works. And there are many other blogs on functional programming that can explain the basics of how it can be used. But in this post I want to look at examples of reduce from real, production, Elixir code. And from these examples I want to extract some useful patterns that you can be used in new code that we will write in the future.

The first example comes from the ExDoc project:

ExDoc

# From ex_doc/lib/ex_doc/retriever.ex
# Returns a dict of { name, arity } -> [ behaviour_module ].
defp callbacks_implemented_by(module) do
  behaviours_implemented_by(module)
  |> Enum.map(fn behaviour -> Enum.map(callbacks_of(behaviour), &{ &1, behaviour }) end)
  |> Enum.reduce(%{}, &Enum.into/2)
end

There is a lot going on here. The high level pattern is:

Enum.map(f1) |> Enum.reduce(f2)

which is the famous map-reduce pattern. In ExDoc’s particular case, Enum.reduce is used to reduce into a map which leads to the second pattern - the reduce into pattern:

Enum.reduce(enumerable, collectable, &Enum.into/2)

This pattern uses reduce to fill some collectable like a list, stream or map. The pattern can be used, as in ExDoc, to convert a keyword list into a map. The full pattern used by ExDoc

Enum.map(list, list_to_keyword_function) |> Enum.reduce(collectable, &Enum.into/2)

Mix

Mix has many great examples of reduce. In the following section I’ll describe them starting with the simplest and working up to more complex examples.

The first is a classic usage of reduce:

max = Enum.reduce docs, 0, fn({task, _}, acc) ->
  max(byte_size(task), acc)
end

The reduce considers all elements of docs and computes a single value - in this case the maximum byte size. This is the basic usage. More complex uses can build up a more complex data structure than just a value. In this next example we see an Enum.reduce call that builds up a list:

# From elixir/lib/mix/lib/mix/archive.ex:
Enum.reduce evsn ++ ebin ++ priv, [], fn(f, acc) ->
  case File.read(f) do
    {:ok, bin} ->
      [{Path.join(dir, f) |> String.to_char_list, bin}|acc]
    {:error, _} ->
      acc
  end
end

In this case Enum.reduce is being used in a very similar way to Enum.map; to convert one array into another using a mapping function. A simplified or generalized version might look like this:

Enum.reduce list, [], fn(element, acc) ->
  case some_test(f) do
    :ok    -> [ f(element) | acc ]
    :error -> acc
end

With the details removed it is easier to see that the major difference between Enum.map and this use of Enum.reduce is that reduce allows Mix to skip the elements that fail the test. The :ok case is the same as map while the :error case leaves the accumulated value unchanged.

So, the pattern here is

Enum.reduce can be used as a filtering version of Enum.map

Our final example is another function from Mix which uses a beautiful, nested reduce:

# From elixir/lib/mix/lib/mix/compilers/elixir.ex
defp mtimes(entries) do
  Enum.reduce(entries, HashDict.new, fn {_b, _m, source, _d, files, _bin}, dict ->
    Enum.reduce([source|files], dict, fn file, dict ->
      if HashDict.has_key?(dict, file) do
        dict
      else
        HashDict.put(dict, file, Mix.Utils.last_modified(file))
      end
    end)
  end)
end

To understand this function let’s look first at the inner reduce:

Enum.reduce([source|files], dict, fn file, dict ->
  if HashDict.has_key?(dict, file) do
    dict
  else
    HashDict.put(dict, file, Mix.Utils.last_modified(file))
  end
end)

This Enum.reduce builds up dict by inserting files as keys but only if the file is not already present in dict. This is like the reduce into pattern we saw before but uses a filter (which seems to be a common practice in Mix).

The outer reduce does two things

1. It creates a new HashDict to be used as the initial dict in the inner reduce.
2. It reduces over all entries which must be a list (or stream) of tuples which contain the files. The structure of the tuple is not important to the underlying pattern.

So the two patterns I see here are:

Enum.reduce can be used as a filtering version of Enum.into

and

Nested Enum.reduce calls can be used to accumulate a data structure over multiple steps.

Next Steps

When I started writing this post I alredy knew how to use reduce but in looking over these examples and extracting generalized patterns I’ve learned many new ways of using reduce that I hope to be able to apply in my own code in the future. I hope you have also learned something from reading my analysis and description of the patterns.

Next week I plan to continue with this style of analysis and will look for patterns with Streams in Elixir.