Patterns and pattern matching

As conditional expressions are written with cond, pattern matching expressions are written with match. A match expression has the following general form:

Match evaluation is similar to cond evaluation. First the expression exp_0 is evaluated to a value we’ll call v. Then v is compared against each pattern in turn, in the order given: pat_1, then pat_2, and so on, up to pat_k. If v matches pat_1, then the value of the whole expression is exp_1, and evaluation within the match goes no further. If pat_1 doesn’t match, then v is checked against pat_2, and the value is exp_2. Evaluation continues from pattern to pattern until a match is found (or none is).

Consider this match expression:

In this case, (+ 1 1) is evaluated to 2. This is compared first against the first pattern in order, which is a constant pattern 2. This is a match, so the value of the whole expression is the string "A". With the following alteration, the value of the expression is "B":

There are many useful kinds of patterns besides constant patterns: one such kind is variable patterns. A variable pattern consists of a variable name, and a) always succeeds and b) gives a name to the value matched. Consider this example:

The value of this expression is 31. Why? The expression immediately following match evaluates to 30. Then 30 is compared against the variable pattern n, which succeeds in matching (as variable patterns always do) and furthermore binds the name n to the expression’s value. When the expression (+ n 1) is evaluated, n is bound to 30, and we finally arrive at 31.

Because variable patterns always match, they can be used as catch-all or default patterns in a pattern match, playing a role not entirely unlike what else does in the last branch of a cond. For example:

In this expression, the match of evaluated 17 against the constant pattern 0 fails. The match against n necessarily succeeds, and the value of the expression altogether is the string "not zero".

The variable pattern n in the last example is a suitable candidate for a wildcard pattern, written with the underscore character _. Recall that a variable pattern both matches a value and binds a name to it, but in this case (and many cases in practice) the name is not needed, since n is not subsequently used. In such cases as this, a wildcard pattern, informally known as a "don’t care" pattern, is a good choice. A wildcard pattern always succeeds in matching, like a variable pattern does, but doesn’t bind; that is, it associates no name with the matched value.

The underscore serves not only to catch any expression that falls past the constant pattern 0, but it also expresses clearly that the particular value of the matching expression is of no interest, only the fact that it did not match any previous pattern.

Matching against structures is a convenient way to, first, identify the particular struct under consideration, and also to name the individual components in the structure and thereby eliminate calls to selectors.

Define a point in 2-space as follows:

Now assume there exists an expression of type Point bound to a variable p, and consider the following match:

This expression performs the (admittedly contrived) operation of adding together the x and y components of the point p. The pattern (Point x y) serves several purposes: Point ensures that p is actually a Point struct, and furthermore the names x and y are bound to its two components. Syntactically, this is a real bargain, although it will take practice and experience to appreciate why. Without pattern matching, a similar expression looks like this:

On the whole, the latter expression is no longer (in number of characters) than the first; however, in the part of the expression where the action is — namely, where x and y are added together — the former expression is a clean (+ x y), while the latter is cluttered up with selectors (Point-x and Point-y). Pattern matching often has this clarifying effect by separating the deconstruction of a compound value from computing with its elements.

Using nested patterns with nested structures pushes the advantages of structure matching still further. Consider a line segment structure containing two points as follows:

Now we consider the following (contrived) computation: to subtract the product of the segments y components from the product of its x components. We can write the expression with nested patterns like this:

Compare that expression to this one that uses selectors:

In the second expression, the selectors overwhelm the syntax and make reading and understanding the expression (comparatively) difficult; the matched alternative above (- (* ax bx) (* ay by)) is crystal clear by comparison.

Note also that this second example of pattern matching illustrates that the variable names to which values from within a structure are bound do not need to have the same names as the fields. While in the first example, we found it convenient to use x as the name for the contents of the x field of the structure, in the second example, we chose the names ax and bx.

Pattern matching is especially useful in the definition of functions. Here is a function definition using only selectors:

When we rewrite the function using a match, the code is not shorter, but its main expression is free of selectors and hence clearer:

With nested structures, nested pattern matching cleans up and clarifies the computation to an even greater extent. The following two functions compute the same property of a line segment; compare the syntax of one to the other.

Recall the definition of the Shape type from Chapter 5.

We can use pattern matching to write functions that work over union types like Shape. For example, the shape-color function can be written using pattern matching as

We use wild cards for the parts of the shapes that we are not interested in.

You have to be careful to avoid using the identifiers true, false, and empty in patterns. These identifiers are variables (not literals), which means that they will match any value. For example, the following function will always return false.

What happens here is that the value of b is assigned to a new variable named true, rather than being matched to the value true. The expression then results in false, the expression part of the first match.

The correct way to write it is to use the #f and #t literals in the patterns:

Another common mistake with pattern matching is assuming that a successful match induces type information the way that type filters for type tests do. For example, the following function will result in a type error

Even though matching shape against the Circle pattern is only possible if shape has the Circle type, the flow-sensitivity of Typed Racket’s type system does not extend to pattern matching. Likewise, even though failing to match the Circle pattern is only possible if shape has type Rect, the Typed Racket type checker is not clever enough to realize that fact.