Matching a List

A list is a common data structure. You’ll have lists of customers, orders, players, etc. You will need to process lists a lot. Because of how often you’ll be working with them, let’s spend a little more time talking about a different way to think about lists.

Lists are Freaky Little Snakes

Lists are very different from Arrays in other languages. They look deceptively similar. I think it helps to think about lists as snakes. A normal cute little snake. Not the scary kind at all.

There are 2 parts to this snake. The “head” and the “tail”.

Now imagine the snake has consumed a sequence of numbers. The first one eaten is the furthest inside. The last one eaten is still in the head.

I want to process this list and pull off the “head” value. Using a Pattern Match, I can cut off the head of the snake and break it into the two parts “head” and “tail”.

I’ve detached the head from the tail. Now the freaky part! The tail grows a new head!

In this way a list is recursive. When you remove the head, the tail is a new list and so has a head of its own!

Tools of the Trade

The square brackets and pipe characters (ie. [, |, ]) are very useful when working with lists.

They can be used to add a new element to the front of a list:

existing = [2, 3, 4]
[1 | existing]
#=> [1, 2, 3, 4]

The same characters can be used in a Pattern Match to destructure a list and separate the list’s head from the tail.

existing = [1, 2, 3, 4]
[head | tail] = existing

head
#=> 1
tail
#=> [2, 3, 4]

Here we’re going to focus on using this tool for pattern matching.

Lists Matching

Let’s look at some examples for pattern matching a list.

What if I want to pull off the head of the list but I don’t care about the rest of the list. I only want the head. I might try this:

[head] = [1, 2, 3, 4, 5]
#=> ** (MatchError) no match of right hand side value: [1, 2, 3, 4, 5]

This won’t work because the pattern I defined on the left says it is a 1 element list. But that’s not what I want. By using the pipe | I can separate the head from the tail. Since I don’t care about the tail, I’ll use the underscore _ to ignore it.

[head | _tail] = [1, 2, 3, 4, 5]

head
#=> 1

With this pattern I’m saying, “Bind the list’s head to head and ignore the rest”.

If I have a list of length 1, what happens? There are no numbers in the tail.

[head | tail] = [1]

head
#=> 1
tail
#=> []

Remember a list is recursive. Even when there is nothing in the tail, I will receive a new list. In this case, it happens to be empty. This allows me to Pattern Match a list with only 1 element in it too.

If I explicitly want to match against a list with only 1 element in it, I can this way:

[first] = [1] 

first
#=> 1

Multiple Heads?

You are not limited to only putting 1 element in the head portion of the pattern [head | tail]. You just need to comma separate them.

[a, b, c | rest] = [1, 2, 3, 4, 5]

a
#=> 1
b
#=> 2
c
#=> 3
rest
#=> [4, 5]

The pattern [a, b, c | rest] says, “With a list of at least 3 elements, bind the 1st to a, the 2nd to b, the 3rd to c and whatever remains bind to rest.” So this pattern will not match a list with two or fewer elements.

[a, b, c | rest] = [1, 2]
#=> ** (MatchError) no match of right hand side value: [1, 2]

[a, b, c | rest] = [1]
#=> ** (MatchError) no match of right hand side value: [1]

[a, b, c | rest] = []
#=> ** (MatchError) no match of right hand side value: []

Matching an Empty List

If you want to match that a list is actually empty, the pattern to use is an empty list [].

[] = []

Using the pattern [head | tail] with an empty list fails.

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

The pattern is saying, “It must be a list with at least 1 element in it. It can have more, but must have at least 1.”

Matching to an Exact Sized List

We saw how you can match to “at least” a number by including the | and a variable or placeholder in the tail position. You can also match against an exact number. This is a pattern that more explicitly defines the shape of the list.

[a] = [1]

a
#=> 1

[a, b] = [1, 2]

a
#=> 1
b
#=> 2

[a, b, c] = [1, 2, 3]

a
#=> 1
b
#=> 2
c
#=> 3

Matching Values in the List

We can also be more explicit about the shape of the list by giving a pattern that includes explicit values.

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

rest
#=> [2, 3, 4]

This pattern says, “It must be a list with at least 1 element and it starts with a 1.” This pattern won’t match a list that starts with something other than a 1.

[1 | rest] = [2, 3, 4]
#=> ** (MatchError) no match of right hand side value: [2, 3, 4]

Pin Operator Matching Values

We can also use the Pin Operator ^ to describe a pattern.

head = 12
[^head | rest] = [12, 13, 14, 15]

rest
#=> [13, 14, 15]

head = 0
[^head | rest] = [12, 13, 14, 15]
#=> ** (MatchError) no match of right hand side value: [12, 13, 14, 15]

This pattern says, “It must be a list with at least 1 element and the first element must be the value bound to the head variable. Bind whatever else is there to the rest variable.”

Recap

Quick review of some important properties of pattern matching a List.

• A List is recursive. When we pull off the “head”, the “tail” is itself a list.
• We can specify patterns that a list must match an exact number of elements or “at least” a number of elements.
• We can use explicit value to define the shape of the data.
• We can use the Pin Operator to define the shape of the data.

Understanding how to Pattern Match lists lets us do some pretty cool things. One cool thing is we can recursively process a whole list using pattern matching without using a for or while style loop.