How to Use Head and Tail in Elixir

24 January 2023 by Adam Davis

Table of contents:

Head and tail are a common programming concept used to represent a linked list. While not unique to Elixir lang, it is crucial for understanding the language’s representation of lists.

What do head and tail refer to?

The head of a list is the first element, and the tail is the list containing all the remaining elements.

For example in the list [1, 2, 3, 4], the head would be 1 and the tail would be the list [2, 3, 4].

Head and tail are a recursive representation

If you noticed in the example above, we started with a list, but the tail of that list is also a list that has its own head and tail. This is also true of the tail’s tail, and so on.

What are the head and tail of a list with only one element?

The head of a single element list would be the only element in the list, and the tail would be an empty list.

What are the head and tail of an empty list?

An empty list does not have a head or tail.

How do I get the head and tail of a list in Elixir?

Method 1: hd and tl

The simplest way to get the head or tail in Elixir is with hd/1 or tl/1 respectively:

iex> hd [1, 2, 3]
1
iex> tl [1, 2, 3]
[2, 3]

If we call hd/1 or tl/1 with an empty list, you’ll be given an ArgumentError.

iex> hd []
** (ArgumentError) errors were found at the given arguments:

  * 1st argument: not a nonempty list

    :erlang.hd([])
iex> tl []
** (ArgumentError) errors were found at the given arguments:

  * 1st argument: not a nonempty list

    :erlang.tl([])

Method 2: Pattern matching

To get both head and tail at once, we can use the | operator for pattern matching:

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

But if we only need one of the values, we can still use pattern matching. Just use an underscore to ignore the other value:

iex> [_ | tail] = [1, 2, 3]
[1, 2, 3]

If we try to pattern match head and tail on an empty list, we’ll be given a MatchError.

iex> [head | tail] = []
** (MatchError) no match of right hand side value: []

How to pattern match with head and tail in an Elixir function header

The pattern matching shown above can also be used in a function header to verify that a list is non-empty, while also extracting whichever values you need.

We can test this out by making a function that pattern matches on head and tail, and an overloaded function of the same name that accepts any argument.

def pattern_match_test([_head | _tail]) do
  "pattern match succeeded"
end

def pattern_match_test(_) do
  "pattern match failed"
end

We can see that if we call pattern_match_test/1 with a non-empty list we get the result from the pattern match function, but other types of input will fail the pattern match.

iex> pattern_match_test([1, 2, 3])
"pattern match succeeded"

iex> pattern_match_test([])
"pattern match failed"

iex> pattern_match_test("asdf")
"pattern match failed"

How to use head and tail to add an element to a list in Elixir

Elixir’s head and tail syntax can also be used to add an element to a list.

iex> [1 | [2, 3]]
[1, 2, 3]

The above example shows how we can prepend an element to a list. However, trying to append an element to the end can produce some unexpected results:

iex> [[1, 2] | 3]
[[1, 2] | 3]

This is because the syntax only really supports prepending a head element instead of appending a tail. This is to encourage more efficient operations, because with a linked list is is much faster to add an element to the front of the list instead of the end.

In order to prepend an element, the new node needs to be created and then pointed at the existing list, which becomes the tail.

However, to add an element to the end of a list, we must traverse every element and then point the existing last node of the list to the new element.

It likely wouldn’t cause any issues to add an element to the end of a list once or twice, but if we had a large operation where we appended elements thousands of times the inefficiency would compound.

Real world example: Let’s implement filter!

To put everything together that we’ve learned in this post, we’re going to create an implementation of filter/2 using head and tail.

As with most recursive functions, I like to start with defining a base case. We’ll continue the recursive calls as long as the head is not nil. Once it is nil, we’ll return the reverse order of the list.

def my_filter ([head | tail], f, acc) when head != nil do
	# TODO: implement
end

def my_filter(_list, _f, acc) do
  Enum.reverse(acc)
end

Next we need to define what happens in the recursive case when there is an element in the head of the list. If the function f produces a value of true when given the head of the list, when it should be pushed onto the accumulator. Otherwise, we should keep the accumulator as-is. In both cases, we need to make a recursive call.

def my_filter([head | tail], f, acc) when head != nil do
  if f.(head) do
    my_filter(tail, f, [head | acc])
  else
    my_filter(tail, f, acc)
  end
end

Finally, we need to define the user interface. Because the user doesn’t need to know about the existence of the accumulator, we make a separate function header that does not include the ability to set the accumulator.

def my_filter(list, f) do
  my_filter(list, f, [])
end

To provide a neater interface, we should make every function private except the one we want the user to call.

def my_filter(list, f) do
  my_filter(list, f, [])
end

defp my_filter([head | tail], f, acc) when head != nil do
  if f.(head) do
    my_filter(tail, f, [head | acc])
  else
    my_filter(tail, f, acc)
  end
end

defp my_filter(_list, _f, acc) do
  Enum.reverse(acc)
end

Now let’s test it:

iex> my_filter([1,2,3,4], fn x -> x > 1 end)
[2, 3, 4]

It works!

Now that you’ve read this post and implemented filter, you should have a firm grasp of how to use head and tail in Elixir.

Adam Davis

Share this post: