Jun 06, 2016
Table of contents:
Last week we looked at branching and conditionals logic and how we can rewrite these constructs as multi-clause functions to make our code more declarative and easier to understand and read.
If you are coming to Elixir from another programming language you are probably very accustomed to using loops to iterate through a list of items.
Something that may surprise you about Elixir is, there are no constructs for
Instead, Elixir prefers to use recursion to achieve dynamic looping. In today’s tutorial we will look at recursion.
So if we don’t have the
while construct in Elixir, how do you iterate through a list?
The answer is our new favourite partnership of pattern matching and multi-clause functions!
First you define the clause that will be the last step of the process. Typically this will handle the situation when the list is empty.
Next you define more generic clauses that you can call recursively to iterate through the list.
For example, imagine we have a module that will print each element of a list:
defmodule MyList do def read(), do: IO.puts("End of list") def read([head | tail]) do IO.puts(head) read(tail) end end
Firstly, we define a function that will deal with the last step of the process. In this example we have a
read/1 function that matches an empty list. If the list is empty we will print a message to alert the user.
Second, we define a more generic function that accepts a non-empty list.
We pattern match the list into the
head and the
tail and we print the
Finally we call the
read/1 function again with the
tail contains elements it will pattern match against the second definition. But if the list is empty the call to the
read/1 function will pattern match to the first definition which will print the final message and end the recursion.
So as you can see, we can effectively loop through the list using pattern matching, multi-clause functions and recursively calling the same function.
Again, as with last week, although this involves writing multiple functions, this approach has many benefits.
Firstly, your code is a lot more declarative. You can see what will happen when the list is empty verses if the list is not empty.
And secondly you can deal with each step of the process as a single, simple function definition.
If you’ve ever read into functional programming you may have heard the term “Tail Call Optimisation”. Unless you’ve really been digging into a functional programming language in the past, you have probably no idea what this even means, I know I certainly didn’t!
I’ll try and explain the concept here.
When you recursively call a function, the computer will allocate memory for every element in the list. This is probably going to be fine for a small list, but in the case of a really big list, you might run out of memory!
For example, here is an example of a Module for adding each element of a list together and return the total:
defmodule MyList do def sum(), do: 0 def sum([head | tail]) do head + sum(tail) end end MyList.sum([1, 2, 3]) |> IO.puts()
As you can see, first we define the empty list clause. In this case we return
0 for an empty list.
Next we define the non-empty clause that will be recursively called. This function splits the list into the
head and the
tail and then it returns the value of adding the
head and the return value from the
sum/1 function when given the
If you run this code you should see it produce the correct answer of
So what’s the problem with this and where does Tail Call Optimisation come in?
If you were to run this function with a very big list of numbers you would eventually run out of memory. As I mentioned earlier, this is because the computer needs to allocate memory for each element in the list as the function is called recursively.
The solution to this problem is to slightly rewrite the function to take advantage of Tail Call Optimisation.
Tall Call Optimisation is where if the last thing a function does is call another function, the compiler can jump to the other function and then back again without allocating any additional memory.
The Erlang compiler will do this automatically because it will recognise the tail call, we just need to write out code in a certain way to take advantage of this optimisation.
This is great for recursive functions because it can run for a very large list without allocating any additional memory.
The reason why the example from above does not take advantage of tail call optimisation is because the last thing that occurs in the function is not a call to another function.
def sum([head | tail]) do head + sum(tail) end
As you can see, the last thing that happens is the addition between the return value from the
sum/1 call and the
Lets rewrite this function to take advantage of tail call optimisation:
defmodule MyList do def sum(, accumulator), do: accumulator def sum([head | tail], accumulator) do sum(tail, head + accumulator) end end MyList.sum([1, 2, 3], 0) |> IO.puts()
First we define the
sum/1 empty list clause that will simply return the accumulator that is passed in.
Next we define the non-empty list clause that will recursively call itself, each time taking the
head and adding it to the
accumlator until the list is empty.
Lets take a look at a couple of more examples of writing recursive functions in Elixir.
First, here is an example of doubling each value in a list:
defmodule MyList do def double(), do:  def double([head | tail]) do [head * 2 | double(tail)] end end
This is pretty similar to the previous examples but instead of passing an accumulator we just return a new list with the head multiplied by 2.
Next, here is an example of only returning the even values from a list:
defmodule MyList do def evens(), do:  def evens([head | tail]) when rem(head, 2) == 0 do [head | evens(tail)] end def evens([_ | tail]) do evens(tail) end end
Once again we first define the empty-list clause.
Next we define a clause that matches a non-empty list, but only when the
head is an even number. We then return a new list with the
head and a recursive call with the remaining tail.
Next we define the clause for a non-empty list when the
head is not an even number. Here we don’t care about the
head so we can just recursively call the
evens function with the remaining tail.
Finally, here is an example of a
map/2 function that takes a list an an anonymous function that will be applied to each element of the list:
defmodule MyList do def map(, _), do:  def map([head | tail], func) do [func.(head) | map(tail, func)] end end MyList.map([1, 2, 3], &(&1 * &1))
Once again we first define the empty state clause that will simply return the empty list.
Next we define the general non-empty clause that will call the function on the head and then pass the tail and the function back into the
map/2 function to be called recursively until the list is empty.
The anonymous function in this example will simply multiply each element by itself.
If this anonymous function definition looks a bit strange to you, take a look at Functions as First-Class Citizens in Elixir.
Recursion is an important aspect of learning Elixir and is probably not something you do that often if you are coming from from another programming language.
Tail call optimisation is another important thing to understand as you could come across a situation where you are running out or memory due to how memory is allocated for each element of your list.
However, you probably won’t write these types of functions because they’re already available to you via the
Enum module. But it’s still worth understanding what’s going on in case you do.