Heads vs. Tails: List Recursion in Elixir

When you hear the word “list” in relation to some programming languages you might automatically think of arrays. This is not the case with Elixir, which treats lists as a linked data structure. Elixir defines a list as follows:

A list may either be empty or consist of a head and a tail. The head contains a value and the tail is itself a list. — Programming Elixir by Dave Thomas

What this means is that if you have a list, such as [1, 2, 3], what you really have is a head with a value of one pointing to a tail ([2, 3]) which is itself a list. This makes it easy to traverse linearly, but expensive to access a random index, since it must first traverse through all previous elements. This head/tail pattern can be represented with the pipe syntax:

[ head | tail ]
as applied to our list [1, 2, 3]: 
[ 1 | [2, 3] ]

What then are lists useful for? The answer is recursion, which allows us to do some really interesting operations. Let’s look at Dave Thomas’ example in Programming Elixir for finding the length of a list recursively.

defmodule MyList do
   def len([]), do: 0
   def len([head|tail]), do: 1 + len(tail)
end

Something to know before diving into the recursive behavior of the function above is how…