# Learning How to Loop in Elixir Through Recursion

Last reviewed on January 13, 2019

For the past 10 years, my programming experience has mostly focussed on JavaScript and PHP. I've learned a few functional programming concepts through JavaScript, such as function purity, immutability, and side effects, but I've never worked with a true functional language. To learn more about functional programming, I've decided to learn Elixir and write about what I learn to help me learn.

## Looping in Elixir

Elixir doesn’t have looping constructs like a `for` loop or a `while` loop. Instead, looping is achieved through recursion. If you’re not familiar with recursion, recursion is when a function keeps calling itself until some condition is met.

Fire up an `iex` session and type in the following:

``````[head | tail] = [1, 2, 3]
tail # [2, 3]``````

Here we’ve pattern matched against the list using the cons operator (the `"|"` character). `head` is the first item in the list and `tail` is a list of all the other items. We could continue and break down `tail` until it is an empty list. For example:

``````[head | tail] = [1, 2, 3]
tail # [2, 3]

tail # [3]

tail # []``````

We can write a recursive function that uses the technique above to go through every item in the list and print out each number:

``````defmodule MyEnum do
each(tail)
end

def each([]), do: nil
end

MyEnum.each([1, 2, 3])``````

In Elixir, functions can have multiple clauses. If a function has multiple clauses, Elixir will try each one from top to bottom in the module until one of them matches.

In the example above, we’ve defined two clauses for the `each` function. The first function clause will match whenever the first argument is a non-empty list, resulting in it getting called. This function will keep calling itself with `tail`, which contains one less item on each successive call, until the list is empty, at which point the second clause will match and get called and the recursion will terminate.

The built-in `Enum` module has a function called `each/2` that makes the above more generic and reusable. `Enum.each/2` goes through every item in a list using recursion behind the scenes and invokes an anonymous function with each item as its argument. This is similar to `Array.prototype.forEach` in JavaScript. Here is an example:

``````Enum.each [1, 2, 3], fn(x) ->
IO.puts(x)
end

# 1
# 2
# 3``````

## Rebuilding `Enum.each/2`

``````defmodule MyEnum do
def each([head | tail], func) do
each(tail, func)
end

def each([], _func), do: nil
end

MyEnum.each [1, 2, 3], fn(x) ->
IO.puts(x)
end``````

Our implementation is very similar to our previous example. The only difference is that we’ve replaced `IO.puts(head)` with `func.(head)` to make it more generic and reusable.

Pretty neat, huh? Now let’s write our own implementation of `Enum.reduce/3`!

## Rebuilding `Enum.reduce/3`

If you aren’t familiar with reduce, it is a way to reduce a list to a single value. Summing an array of numbers is one example. In Elixir, we can use `Enum.reduce/3`. For example:

``````sum = Enum.reduce [1, 2, 3], 0, fn(x, total) ->
x + total
end

sum # 6``````

This works similar to `Array.prototype.reduce` in JavaScript if you’ve seen it there. Here is what the implementation might look like:

``````defmodule MyEnum do
def reduce([head | tail], total, func) do
reduce(tail, new_total, func)
end

def reduce([], total, _func), do: total
end

sum = MyEnum.reduce [1, 2, 3], 0, fn(x, total) ->
x + total
end``````

This example is pretty similar to the `each` implementation that we did previously. Here, we invoke `func` with each item and the accumulating total, which starts off at 0. This returns `new_total`, which is passed into each recursive call. When `reduce` is eventually called with an empty list, the second clause of `reduce` will match, at which point the recursion still stop and `total` will be returned.

Let’s move on and write our own implementation of `Enum.map/2`.

## Rebuilding `Enum.map/2`

If you haven’t used a map function before, it is used to map one list to another list. For example, we can double a list of numbers by calling `Enum.map/2`:

``````doubled_numbers = Enum.map [1, 2, 3], fn(x) ->
x * 2
end

doubled_numbers # [2, 4, 6]``````

As we’ve learned, we can use the cons operator to destructure a list into two parts, the head, which is the first item, and the tail, which is another list of all remaining items.

``````[head | tail] = [1, 2, 3]
tail # [2, 3]``````

We can also use the cons operator to reconstruct a new list from a single value and another list:

``````[1 | [2, 3]] # [1, 2, 3]
[1 | [2 | [3, 4]]] # [1, 2, 3, 4]
[1 | []] # [1]
[1 | [2, 3]] == [1, 2, 3] # true``````

With this in mind, we can rebuild `Enum.map/2`:

``````defmodule MyEnum do
def map([head | tail], func) do
end

def map([], _func), do: []
end

MyEnum.map [1, 2, 3], fn(x) ->
x * 2
end``````

In this example, we are taking the list `[1, 2, 3]` and mapping it to `[2 | [4 | [6 | []]]]`, which is the same as `[2, 4, 6]`.

Let’s move on to our last Enum function and rebuild `Enum.filter/2`.

## Rebuilding `Enum.filter/2`

The filter function is used to take one list and filter it down by some condition which is represented as a function. The function is called for every item in the list. If the function returns a truthy value, that item is kept in the list. If the function returns a falsy value, that item doesn’t make it into the new list. Here is an example using the built-in `Enum.filter/2`:

``````filtered_items = Enum.filter [1, 2, 3, 4, 5], fn(x) ->
x >= 3
end

filtered_items # [3, 4, 5]``````

Here is our own implementation:

``````defmodule MyEnum do
def filter([head | tail], func) do

if result do
else
filter(tail, func)
end
end

def filter([], _func), do: []
end

MyEnum.filter [1, 2, 3, 4, 5], fn(x) ->
x >= 3
end``````

The implementation is similar to our map function, but with an extra `if` statement. If `result` is truthy, we use the cons operator to include it in the list and call `filter` again with the tail. If `result` is falsy, we just call filter again and disregard `head`. We keep doing this until the list is empty, at which point the second `filter` clause will get executed and end the recursion.

## Conclusion

I found reimplementing `Enum.each/2`, `Enum.reduce/3`, `Enum.map/2`, and `Enum.filter/2` a great exercise to learn how to loop in Elixir through recursion. I’m sure these functions in the `Enum` module do more than our implementations, so you should still use those, but nevertheless it is a fun exercise to learn Elixir.