Lists, and matching on their shape

One type inside, in order

A list holds values of one type, in order. [3, 9, 4] is a list of Int, and it can be any length, including none at all: the empty list is written [] and it is an ordinary value, not a failure.

A list is built by joining a value to an existing list with the colon operator, so [3, 9, 4] is short for 3 : (9 : (4 : [])). The empty list sits at the end of every list, which is why walking a list is so easy to write.

Text is a list of characters

A String is a list of Char, so every list idea in this course also works on text. reverse "drawer" answers the text reward, and length counts the letters. This is a fact about the language, not a figure of speech.

Matching on the shape

You can ask what shape a list has by writing the two cases as separate equations. The empty list matches []; anything else matches the pattern x : xs, which names the first value and the remaining list.

The same trick works on a list of a known short length: [x] matches a list with exactly one value. The equations are tried from the top, so the specific shapes go above the general ones.

Taking a list apart

xs :: [Int]
xs = [3, 9, 4]

second :: [Int] -> Int
second (_ : y : _) = y

front :: [Int]
front = take 2 xs

behind :: [Int]
behind = drop 1 xs

Colon on the right, append on the left

The colon takes one value and one list, and it groups to the right: 1 : 2 : 3 : [] is 1 : (2 : (3 : [])). That is why a pattern can peel one value off the front and hand you the rest, and why there is no equally cheap way to peel one off the end.

++ takes two lists. It has to walk the whole of its left argument to find the end and attach the right one, so [1, 2] ++ [3] does more work than 3 : [1, 2]. Both answer a list; only one of them has to look at the values already there.

This is why the recursive functions in the chapters ahead always take the first value and recurse on the tail. The shape of the data decides which end is cheap.

Ranges, and asking for more than there is

[1 .. 5] is the whole numbers from 1 to 5 inclusive, and [2, 4 .. 10] uses the gap between the first two values as the step, giving 2, 4, 6, 8 and 10. The step may be negative, and a range whose ends face the wrong way is simply empty. [1 ..] has no end at all, and it is only usable because the language is lazy: take stops asking after the values it needs.

take and drop are forgiving on purpose: take 5 [1, 2] answers [1, 2] rather than failing, and drop 5 [1, 2] answers []. head is the one that is not forgiving, because there is no sensible value to invent for an empty list.

Patterns must cover every shape

Pattern matching is checked for coverage. A function over a list with equations for [] and x : xs handles every list, because those are the only two shapes a list can have. A function with only x : xs still compiles, with a warning, and then stops the program the first time it meets an empty list.

The wildcard _ is how a pattern says that a part does not matter. (x : _) names the first value and ignores the rest; (_ : y : _) names the second and ignores the first. Using _ instead of an invented name is not just tidier: it tells the compiler that the value is unused, so it will not warn about a name that is never read.

Order is part of the meaning. The equations are tried from the top, so x : xs above [] would never let the empty case run, and the compiler reports the second equation as redundant.

Try these next

• Build [10, 20, 30] with the colon only, then print it and check the brackets are where you expect.
• Print take 3 and drop 3 of a five-value list, and predict both before you run.
• Make a descending range with a negative step, and print its length and its reverse.