In this post we are going to look at how lists are implemented in Elixir and how looking at its source code can teach us a thing or two about the language.
When you program in Elixir you deal with lists all the time. The most common way to specify a list is between square brackets.
$> my_list = [1, 3, 5, 7] # <= a list of integers
Internally lists are represented as a pair consisting of a ‘head’ and a ‘tail’. This is known as a ‘linked list’.
[ head | tail ]
If we pattern match on the list above we get
$> [ head | tail ] = [1, 3, 5, 7] [1, 3, 5, 7] $> head 1 $> tail [3, 5, 7]
The head is the integer
1, and the tail is itself a linked list. We could also write this list as,
[ 1 | [ 3 | [ 5 | [ 7 |  ] ] ] ]
That’s a syntactically correct but verbose way to do it. I use it to show the structure of a list. It’s important to note the last part of the pairing is itself an empty list
. Note, there is also an ‘improper list’ not ending in an empty list, let’s ignore that for now.
When you write a list, it’s a list of linked lists all the way down.
The idiomatic way to add to the start of a list is
$> new_list = [ 0 | my_list ] [ 0, 1, 3, 5, 7 ]
If you want to add to a list in anywhere other than its start, you can use
List.insert_at/3. If you are interested to see how Elixir implements this insertion we can look at the source.
One of the beauties of Elixir is the bulk of it is written in Elixir. Looking at its source is therefore something I highly recommend. You can learn a lot from seeing how the language authors structure the code. Let’s take a look at
First off, let’s define the function’s specification.
@spec insert_at(list, integer, any) :: list insert_at(list, index, value)
So, we pass in the
list we want to add to, the
index (as an integer) and the
value we want to add. We get a
list in return. Importantly the integer can be negative or positive. The value can be of any type.
The definition of
def insert_at(list, index, value) when is_integer(index) do if index < 0 do do_insert_at(list, length(list) + index + 1, value) else do_insert_at(list, index, value) end end
We’ll dig into it momentarily. In our example we are going to add another integer to the end of the list.
$> newer_list = List.insert_at(new_list, -1, 9)
The documentation points out: “… that
index is capped at the list length. Negative indices indicate an offset from the end of the
So, here we are using
-1 as our
index to add to the end of the
list. We could have also used
5 as the
index to achieve the same thing, however, we need to know the length of the
list to do that. As the caller of the function we don’t want/have/need to check the list’s length when we have
-1 at our disposal. The function will call the length function too, so it would be mighty redundant.
Looking back at the definition, when called it checks that
index is an integer as a guard in the function head. It then performs a conditional check on the
Both branches of the conditional call the same (private) method, but negative integers are manipulated before the call is made. In our case we pass in
-1 and the first branch of the conditional is triggered.
Substituting the values
do_insert_at (the private function) is called thus
do_insert_at([ 0, 1, 3, 5, 7 ], 5 + -1 + 1, 9) # => do_insert_at([ 0, 1, 3, 5, 7 ], 5, 9)
This is where the fun begins. Like most functional languages, Elixir relies heavily on recursion. Let’s look at
do_insert_at, the private counterpart(s) to
insert_at and see how it puts this oft used technique to work.
defp do_insert_at(, _index, value) do [value] end defp do_insert_at(list, index, value) when index <= 0 do [value | list] end defp do_insert_at([head | tail], index, value) do [head | do_insert_at(tail, index - 1, value)] end
Crikey! There are three definitions. This is an example of Elixir’s pattern matching at work. Let’s imagine they are numbered from 1 to 3 top to bottom to see how they work together.
as the first param, will return
valuewrapped in a list.
indexvalue less than or equal to
0. Returns a list containing
valueappended to the head of
We established that our call to
insert_at results in
do_insert_at being called as
do_insert_at([ 0, 1, 3, 5, 7 ], 5, 9). Let’s step through it.
On the initial call patterns #3 is the first pattern to match and returns
[ 0 | do_insert_at([ 1, 3, 5, 7 ], 4, 9) ]
Let the recursion begin!
I’ll break that down once, it’s going to be used recursively. The body of the function
[head | do_insert_at(tail, index - 1, value)] appends the
head of the
0) to a recursive call to ‘itself’ passing the
[ 1, 3, 5, 7 ]) as the
4 as the
9 as the
This recursive call again matches #3. It returns.
[ 0 | [ 1 | do_insert_at([ 3, 5, 7 ], 3, 9) ] ]
This again matches #3. Returning
[ 0 | [ 1 | [ 3 | do_insert_at([ 5, 7 ], 2, 9) ] ] ]
[ 0 | [ 1 | [ 3 | [ 5 | do_insert_at([ 7 ], 1, 9) ] ] ] ]
[ 0 | [ 1 | [ 3 | [ 5 | [ 7 | do_insert_at(, 0, 9) ] ] ] ] ]
Phew. Now we match #1 because the first parameter is an empty list. A call to #1 returns
[ 0 | [ 1 | [ 3 | [ 5 | [ 7 | [ 9 |  ] ] ] ] ] ]
And although there are a ton of brackets there, it’s valid literal syntax for the list
[ 0, 1, 3, 5, 7, 9 ]. There is no more for Elixir to evaluate and the function returns a new list (don’t forget immutability, the original list remains).
In this example #2 was not called. That’s because we added to the end of the list. The list was at the end when the
index reached zero. If we’d put the new value anywhere else in the list #2 would have matched and returned what was left of the original list with the new value appended to its front.
Hopefully you can see from this example how readable and understandable the source of Elixir can be. Additionally I hope it can give you food for thought on how you might tackle some of your own needs using recursion, pattern matching, guards etc.
If you wanted it to build a product you’d find a way to get time to work on it. If you really wanted to start that new hobby you’d sacrifice something to find the time and money to do it.
I'll define a "Wannabe Entrepreneur" as someone who has never made money from their businesses. Here are the different types of wannabes.
In the past few years I've built go-carts, built a 200+ sq ft workshop, written several eBooks. How do I create a life where I have time to work on side projects?
Receive 5 Software projects mistakes we have made over the years and how to avoid them.