Of all the data structures that you might use in Elixir, the one that you will undoubtly use the most is the list.

In Elixir a list is a what is commonly referred to in other languages as a linked-list and is used to contain a collection of items of all the same type.

What is a list anyhow?

At the most basic, and important level, a list may be empty:

[]

or comprise of a head and a tail:

[ H | T ]

the head (H) is a value, while the tail (T) is the rest of the list - this is a recursive definition. The | character is the join operator that joins the elements of a list together and can be used to construct a list or in pattern matching.

Recursive Definition - what the hell does that mean?

This is best explained using an example: Lets take a list, say:

[1,2,3,4]

Using this list the eagle-eyed amongst you will have already spotted that the head of this list is

1 

and the tail is:

[2,3,4]

This can be represented in the following manner:

[ 1 | [2,3,4] ]

So now you can see that the tail is also a list:

[2,3,4]

Which can be represented as:

[ 2 | [3,4] ]

This carries on to the end:

[ 3 | [4] ]

The last element of this list

[4]

is also a list :

[ 4 | [] ]

at which point the recursion ends. So the list [1,2,3,4] can be represented as:

[ 1 | [ 2 | [ 3 | [ 4 | [] ] ] ] ]

So as you can see from this:

[ H | T ] => H | [T]
[] => []

Using this knowledge, we can now build functions that can recurse over this data structure.

Go on the show me…

Ok, contrived example time.

We’ve come up against a problem where we need to calculate the length of a list. Instead of reaching for the Enum modules count/1 or reverse/1 functions, we decide to roll our own, and whilst we’re at it, we might also need a function to calculate the product of a list of integers.

In a convenient folder on your system create the following file customlist.exs. In that file, enter the following:

defmodule CustomList do
  def len([]), do: 0
  def len([_head|tail]), do: 1 + len(tail) 

  def product([]), do: 1
  def product([head|tail]), do: head * product(tail)

  def reverse(list), do: reverse(list, [])
  defp reverse([], list), do: list
  defp reverse([head|tail], list), do: reverse(tail, [head | list])
end

Lets now fire up IEX and load in the module to demonstrate:

$ iex
Erlang/OTP 17 [erts-6.3] [source-f9282c6] [64-bit] [smp:8:8] [async-threads:10] [hipe] [kernel-poll:false]

Interactive Elixir (1.0.2) - press Ctrl+C to exit (type h() ENTER for help)
iex(1)> c "customlist.exs"
[CustomList]   
iex(2)> CustomList.len([1,2,3,4])
4
iex(3)> CustomList.product([1,2,3,4])
24
iex(4)> CustomList.reverse([1,2,3,4])
[4, 3, 2, 1]

so how do these work then?

well, lets take a look at the first one: CustomList.len/1

  def len([]), do: 0
  def len([_head|tail]), do: 1 + len(tail)

when the list [1,2,3,4] gets passed in, it doesn’t match the first definition, it falls through to the second definition. Here the list gets split into _head = 1 and tail = [2,3,4]. We’re using the underscored variable ‘_head’ because we don’t want the compiler complaining about unused variables in our function.

so:

len([1,2,3,4])          : _head = 1, tail = [2,3,4] => 1 + len([2,3,4])
1 + len(2,3,4]          : _head = 2, tail = [3,4]   => 1 + 1 + len([3,4])
1 + 1 + len([3,4])      : _head = 3, tail = [4]     => 1 + 1 + 1 + len([4])
1 + 1 + 1 + len([4])    : _head = 4, tail = []      => 1 + 1 + 1 + 1 + len([])
1 + 1 + 1 + 1 + len([]) : [] = 0                    => 1 + 1 + 1 + 1 + 0
1 + 1 + 1 + 1 + 0       : 4

The second function, CustomList.product/1 works in a similar manner:

product([1,2,3,4])          : _head = 1, tail = [2,3,4] => 1 * product([2,3,4])
1 * product(2,3,4]          : _head = 2, tail = [3,4]   => 1 * 2 * product([3,4])
1 * 2 * product([3,4])      : _head = 3, tail = [4]     => 1 * 2 * 3 * product([4])
1 * 2 * 3 * product([4])    : _head = 4, tail = []      => 1 * 2 * 3 * 4 * product([])
1 * 2 * 3 * 4 * product([]) : [] = 1                    => 1 * 2 * 3 * 4 * 1
1 * 2 * 3 * 4 * 1           : 24

The third function CustomList.reverse/1 works a little differently, here we’re using this function as an entry point to the private functions with an additional initial argument. This allows us to build up the list as follows:

reverse([1,2,3,4])                      : list = [1,2,3,4]                    => reverse([1,2,3,4], [])
reverse([1,2,3,4], [])                  : head = 1, tail = [2,3,4], list = [] => reverse([2,3,4], [1 | []])
reverse([2,3,4], [1])                   : head = 2, tail = [3,4], list = [1]  => reverse([3,4], [2 | [1 | []]])
reverse([3,4], [2,1])                   : head = 3, tail = [4], list = [2,1]  => reverse([4], [3 | [2 | [1 | []]]])
reverse([4], [3 | [2 | [1 | []]]])      : head = 4, tail = [], list = [3,2,1] => reverse([], [4 | [3 | [2 | [1 | []]]]])
reverse([], [4 | [3 | [2 | [1 | []]]]]) : [] = [4 | [3 | [2 | [1 | []]]]]     => [4,3,2,1]

So this join operator (|), does it only work on one item for the head?

In a word: No.

The join operator can be used to split more than one element in a match, or to join more than one element to the list. i.e.

iex> [ 1, 2, 3 | [4, 5, 6] ]
[1, 2, 3, 4, 5, 6]

This about covers our discussion about lists. There are some interesting things that can be done with lists of lists and pattern-matching but that is beyond the scope of this discussion.