• Introduction
• Articles We've Written
• Alexa
• The Team
• Let's Talk
• eBooks

Looking at Elixir source code with List.insert_at/3

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.

List.insert_at/3

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 List.insert_at/3.

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 insert_at is

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 list.”

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 index value.

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.

1. Used if called with an empty list [] as the first param, will return value wrapped in a list.
2. Used if called with an index value less than or equal to 0. Returns a list containing value appended to the head of list.
3. Used when neither #1 or #2 match. It’s called when the function receives a non-empty list, an index greater than 0 and a value.

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 list (0) to a recursive call to ‘itself’ passing the tail ([ 1, 3, 5, 7 ]) as the list, 4 as the index and 9 as the value.

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) ] ] ]

Again…

  [ 0 | [ 1 | [ 3 | [ 5 | do_insert_at([ 7 ], 1, 9) ] ] ] ]

Once more…

  [ 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.

Share this article via:

Linkedin |

Facebook |

Twitter

LessEverything, Inc. © 2018