Elixir Language Lists Cons Cells


Lists in Elixir are linked lists. This means that each item in a list consists of a value, followed by a pointer to the next item in the list. This is implemented in Elixir using cons cells.

Cons cells are simple data structures with a "left" and a "right" value, or a "head" and a "tail".

A | symbol can be added before the last item in a list to notate an (improper) list with a given head and tail. The following is a single cons cell with 1 as the head and 2 as the tail:

[1 | 2]

The standard Elixir syntax for a list is actually equivalent to writing a chain of nested cons cells:

[1, 2, 3, 4] = [1 | [2 | [3 | [4 | []]]]]

The empty list [] is used as the tail of a cons cell to represent the end of a list.

All lists in Elixir are equivalent to the form [head | tail], where head is the first item of the list and tail is the rest of the list, minus the head.

iex> [head | tail] = [1, 2, 3, 4]
[1, 2, 3, 4]
iex> head
iex> tail
[2, 3, 4]

Using the [head | tail] notation is useful for pattern matching in recursive functions:

def sum([]), do: 0

def sum([head | tail]) do
  head + sum(tail)