Elixir accumulators

In our last post on Elixir we learned a bit about loops. In that post, we implemented a simple algorithm to sum numbers in a list. Today we’ll keep learning about loops in Elixir and learn a new concept that is accumulators.

What are accumulators?

Let’s think about common problems in a software developer’s day. Suppose you need to implement an algorithm that divides the odd and even numbers from a list, as described below.

Given a list of numbers, the algorithm must divide that list into two new lists, one with only even numbers and the other with odd numbers.

Simply put, we can solve this problem using a loop, which will process the original list and two new lists that will receive the categorized number. Think of it as a separation, we’re separating things, which are numbers in this case.

The following pseudocode aims to reproduce the idea.

original_list = [1, 2, 3, 4]
evens_list = []
odds_list = []
each number in original_list do
    if (rest_of_division(number, 2) == 0) do
        evens_list.append(number)
    else
        odds_list.append(number)
    end
end

print(evens_list)
print(odds_list)

By paying attention to the code above, we can understand what accumulators are.

Note that for each number in the original list we check if this number is even (by checking if the rest of the division by 2 is equal to 0), and based on this check we append the number to the designated new list, these lists will accumulate the results of this checking and at the end of the loop, it will be printed.

In this simple case, evens_list and odds_list are our accumulators. The idea will be the same in all cases. We can define accumulators as this type of structure that will store some result of the operation, which can be a list, an integer (such as a sum), a map, or anything else.

Let’s separate odds from evens in Elixir

We can start building the following module structure.

defmodule Accumulators do
    def odds_and_evens(original_list) do
        odds_and_evens_acc(original_list, [], [])
    end

    defp odds_and_evens_acc([head|tail], odds_list, evens_list) do
        :nothing_yet
    end

    defp odds_and_evens_acc([], odds_list, evens_list), do: {odds_list, evens_list}
end

The function odds_and_evens is our facade and the function odds_and_evens_acc is the function that will do the work.

Note that odds_and_evens_acc must take three arguments, the first is the original list to separate and both the second and third are our odd and even accumulators respectively.

We can see that in the first call, which happens inside our facade function, our accumulators are empty as shown in the pseudocode.

Also, note that our function odds_and_evens_acc has two clauses. The first clause will deal with loop operations and the second clause will run when the loop ends (when all items have been tested) and will return a tuple with odds and evens.

Let’s test if a number is even or odd

To implement the loop body we can use the basic pattern of list processing through recursion. We can see it on our function odds_and_evens_acc that separates the input list in head and tail.

We need to check if head is even or odd and accumulate it in the designated list. We can do it using the case structure and the rem function. Our code will be like the one shown below.

defmodule Accumulators do
    def odds_and_evens(original_list) do
        odds_and_evens_acc(original_list, [], [])
    end

    defp odds_and_evens_acc([head|tail], odds_list, evens_list) do
        case rem(head, 2) do
            0 -> :accumulate_even
            1 -> :accumulate_odd
        end
    end

    defp odds_and_evens_acc([], odds_list, evens_list), do: {odds_list, evens_list}
end

We are almost solving this problem, we already know what head is. Keep going.

Let’s populate our accumulators

We’re going to solve this using recursion and the idea is to call odds_and_evens_acc with the remaining list (that is tail) and the two accumulators. We should do something as shown below.

odds_and_evens_acc(tail, odds_list, evens_list) # recursion calling

But we need more, we need to add the head to the designated list and we can do it by using the same pattern head|tail, where the tail will be the designated list.

odds_and_evens_acc(tail, [head|odds_list], evens_list) # recursion calling when head is odd (keeps the evens_list as is)

odds_and_evens_acc(tail, odds_list, [head|evens_list]) # recursion calling when head is even (keeps the odds_list as is)

The idea is to put the head at the top of the designated list and pass it on to the next recursion call. Our full code is shown below.

defmodule Accumulators do
  def odds_and_evens(original_list) do
    odds_and_evens_acc(original_list, [], [])
  end

  defp odds_and_evens_acc([head | tail], odds_list, evens_list) do
    case rem(head, 2) do
      0 -> odds_and_evens_acc(tail, odds_list, [head | evens_list])
      1 -> odds_and_evens_acc(tail, [head | odds_list], evens_list)
    end
  end

  defp odds_and_evens_acc([], odds_list, evens_list), do: {odds_list, evens_list}
end

Running it

Add the complete code in a file and save it with the .ex extension.

After that open the Elixir prompt in the same folder, compile, and run this file. In my case I’ve named it accumulators.ex and in my terminal, I ran the following commands:

iex(1)> c("accumulators.ex")
[Accumulators]
iex(2)> Accumulators.odds_and_evens([])
{[], []}
iex(3)> Accumulators.odds_and_evens([1, 2, 3, 4])
{[3, 1], [4, 2]}
iex(4)> Accumulators.odds_and_evens([1, 3, 5])
{[5, 3, 1], []}
iex(5)> Accumulators.odds_and_evens([10, 20, 22])
{[], [22, 20, 10]}

We are done, our application is separating a list into two new lists as we expect.

Your turn

Note that odds_and_evens returnsodds_list and evens_list in a different order than the original input, this is reversed to be more precise.

If the order is important, you can do this by reversing the two new lists at the end of the loop (the empty list clause).

You can try it using Enum.reverse.

Summary

In this post, we met accumulators. This concept is a required skill when we need to solve this kind of problem and when we need to do some optimizations (we will talk more about it soon).

Try to solve more problems using accumulators. You can do it even in the most simple examples like sum all numbers from a list, try to rewrite the code of the last post, and solve that problem using accumulators.

Let me know if you have any questions and If you liked this content consider sharing it with your friends.

That’s all. See ya!

Interesting links

We are hiring new talents. Do you want to work with us? become@codeminer42.com