Now we can split a list into its head and its tail, and we can construct a list from a value and a list, which become the head and tail of that new list.
So why talk about lists after we talk about modules and functions? Because lists and recursive functions go together like fish and chips. Let’s look at finding the length of a list.
Writing the list-length algorithm in Elixir is easy:
| | defmodule MyList do |
| | def len([]), do: 0 |
| | def len([head|tail]), do: 1 + len(tail) |
| | end |
The only tricky part is the definition of the function’s second variant:
| | def len([ head | tail ]) ... |
This is a pattern match for any nonempty list. When it does match, the variable head will hold the value of the first element of the list, and tail will hold the rest of the list. (And remember that every list is terminated by an empty list, so the tail can be [].)
Let’s see this at work with the list [11, 12, 13, 14, 15]. At each step, we take off the head and add 1 to the length of the tail:
| | len([11,12,13,14,15]) |
| | = 1 + len([12,13,14,15]) |
| | = 1 + 1 + len([13,14,15]) |
| | = 1 + 1 + 1 + len([14,15]) |
| | = 1 + 1 + 1 + 1 + len([15]) |
| | = 1 + 1 + 1 + 1 + 1 + len([]) |
| | = 1 + 1 + 1 + 1 + 1 + 0 |
| | = 5 |
Let’s try our code to see if theory works in practice:
| | iex> c "mylist.exs" |
| | ...mylist.exs:3: variable head is unused |
| | [MyList] |
| | iex> MyList.len([]) |
| | 0 |
| | iex> MyList.len([11,12,13,14,15]) |
| | 5 |
It works, but we have a compilation warning—we never used the variable head in the body of our function. We can fix that, and make our code more explicit, using the special variable _ (underscore), which acts as a placeholder. We can also use an underscore in front of any variable name to turn off the warning if that variable isn’t used. I sometimes like to do this to document the unused parameter.
| | defmodule MyList do |
| | def len([]), do: 0 |
| | def len([ _head | tail ]), do: 1 + len(tail) |
| | end |
When we compile, the warning is gone. (However, if you compile the second version of MyList, you may get a warning about “redefining module MyList.” This is just Elixir being cautious.)
| | iex> c "mylist1.exs" |
| | [MyList] |
| | iex> MyList.len([1,2,3,4,5]) |
| | 5 |
| | iex> MyList.len(["cat", "dog"]) |
| | 2 |