# Playing With Fire

Exploring the web one Elixir at a time

# [ ] or Lists

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 listanyhow?

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 thatmean?

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 showme…

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 reverse(list), do: reverse(list, [])
defp reverse([], list), do: 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 thehead?

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.