Reduce and map algorithms

Let’s now see how we can use the power of recursion to sum a list of numbers:

defmodule Math do
  def sum_list([head|tail], accumulator) do
    sum_list(tail, head + accumulator)
  end

  def sum_list([], accumulator) do
    accumulator
  end
end

IO.puts Math.sum_list([1, 2, 3], 0) #=> 6

We invoke sum_list with the list [1, 2, 3] and the initial value 0 as arguments. We will try each clause until we find one that matches according to the pattern matching rules. In this case, the list [1, 2, 3] matches against [head|tail] which binds head to 1 and tail to [2, 3]; accumulator is set to 0.

Then, we add the head of the list to the accumulator head + accumulator and call sum_list again, recursively, passing the tail of the list as its first argument. The tail will once again match [head|tail] until the list is empty, as seen below:

sum_list [1, 2, 3], 0
sum_list [2, 3], 1
sum_list [3], 3
sum_list [], 6

When the list is empty, it will match the final clause which returns the final result of 6.

The process of taking a list and reducing it down to one value is known as a reduce algorithm and is central to functional programming.

What if we instead want to double all of the values in our list?

defmodule Math do
  def double_each([head|tail]) do
    [head * 2|double_each(tail)]
  end

  def double_each([]) do
    []
  end
end

iex math.exs

iex> Math.double_each([1, 2, 3]) #=> [2, 4, 6]

Here we have used recursion to traverse a list, doubling each element and returning a new list. The process of taking a list and mapping over it is known as a map algorithm.

Recursion and tail call optimization are an important part of Elixir and are commonly used to create loops. However, when programming in Elixir you will rarely use recursion as above to manipulate lists.

The Enum module, which we’re going to see in the next chapter, already provides many conveniences for working with lists. For instance, the examples above could be written as:

iex> Enum.reduce([1, 2, 3], 0, fn(x, acc) -> x + acc end)
6
iex> Enum.map([1, 2, 3], fn(x) -> x * 2 end)
[2, 4, 6]

Or, using the capture syntax:

iex> Enum.reduce([1, 2, 3], 0, &+/2)
6
iex> Enum.map([1, 2, 3], &(&1 * 2))
[2, 4, 6]

Let’s take a deeper look at Enumerables and, while we’re at it, their lazy counterpart, Streams.