DEV Community

Cover image for How to Use Head and Tail in Elixir
Adam Davis
Adam Davis

Posted on • Originally published at brewinstallbuzzwords.com

How to Use Head and Tail in Elixir

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 of a linked list

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.

Recursive definition of head of tail

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]
Enter fullscreen mode Exit fullscreen mode

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([])
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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: []
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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"
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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]
Enter fullscreen mode Exit fullscreen mode

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.

Add element to front of linked list

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.

Add element to the end of a linked list

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

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
Enter fullscreen mode Exit fullscreen mode

Now let’s test it:

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

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.

Top comments (1)

Collapse
 
davearonson profile image
Dave Aronson

Appending an item in Elixir is even worse than you portray. We don't just have to traverse each existing item, we have to replace it, so we have all the overhead of object creation and garbage disposal. As my first experiment in combining slides and a video feed, I made this video to explain it: youtube.com/watch?v=-if65RXOQvU