I want to wrap up our discussion of pattern matching by giving a precise

definition of when a pattern matches a value.

And this is a bit more complicated now that we have nested patterns but it leads

to a very natural and elegant recursive definition.

So just to be clear, what I'm doing here is describing the semantics, the

evaluation rules for the part of pattern matching where you have a pattern and you

have a value and you want to know whether they match or not.

So for example the value would be the result of the expression between the word

case and the word of. And then the patterns would be each

branch of the case expression in order. Now these rules also applied when you had

patterns in function bindings or in variable bindings, but the key issue is

here's a pattern, here's a value, do they match, and if they do match, what

variables are introduced and what are those variables bound to?

Okay? So in the presence of nested patterns

this is a recursive definition and we would have one case of this definition

for every way of writing down patterns. So I haven't written an exhaustive list

here on the slide but I think by going through these examples you'll get the

sense of it and you'll get a sense of how pattern matching is itself in the

language definition a recursive procedure.

So let's start with the base cases of that recursion and that's when the

pattern is either a variable or that wildcard, that underscore character.

So, we have a pattern, we have a value. One case of our definition is the pattern

is a variable. If that's the case, the match always

succeeds, no matter what the value is, and we bind the variable to the entire

value v. That makes sense.

The and, the underscore case, the wildcard case, is exactly the same, the

match also always succeeds, and we don't bind anything.

Okay, good the other cases are recursive, they build out of the smaller nesting

patterns. Those nested patterns might be base cases

like variables, that is how our we started using pattern matching or they

could be nested patterns in which case this recursive definition will apply.

So for example, suppose we have a tuple pattern.

So we'll have some pattern of the form P1, P2, up to PN.

Then that will only match values that are also tuples with N values inside of them.

And it will only match if P1 matches V1. P2 matches V2.

And so on, up to PN matching VN. That recursive matching is appealing to

the same recursive definition. So we would use a recursive call, if you

will, to the pattern match procedure. Okay?

Now if all of those sub-patterns, those nested patterns, match then they will all

introduce various bindings of variables to values and the overall pattern will be

the union of all those bindings. So all the variables introduced by P1,

all the variables introduced by P2 up to all the variables introduced by PN.

The one extra rule in pattern matching is you're never allowed to use a variable

more than once. If you try to use the same variable more

than once in a pattern the compiler will reject that and, and tell you directly

that you're not allowed to do that. Let's do one more interesting case.

This is the case for when we're using a constructor.

So on the slide there where you see that capital c, assume that, that is one of

the constructors for some data type that's been previously defined.

So one kind of pattern we can write down is that constructor C, followed by a

nested pattern P1. The nested pattern is often a tuple.

but it doesn't have to be. It can be any kind of pattern.

Now, if we have a constructor with a pattern underneath it.

The only thing that will match is a value that was built out of the same

constructor. And a value that matches the pattern.

So we need the same C an we also need p1 to match z one and then whatever variable

bindings are produced by the recursive match of p1 matching v1 are the variable

bindings that we have for the larger pattern c of p1 with the value c of v1.

So hopefully that gives you a sense of how.

Pattern matching is a recursive procedure.

an we can use this to understand much better.

What it means when these nested patterns are matching against, values of certain

shapes. So here are three examples.

In the first example here, you see A. the pattern.

A Cons onto B, cons onto C, cons onto D. And if you follow the recursive

procedure. Using colon, colon as a constructor.

What we have are the nest in pattern A and then the nest in pattern B cons onto

c cons on to cons onto D and so on recursively.

And what this will end up matching is any list that has greater than or three

elements. Because we will recursively match A

against the first element, B against the second C against the third.

And then D against the rest of the list. If the list is too short.

We'll end up trying to match the empty list constructor value against the cons

constructor pattern, that simply fails to match.

That's okay, we would move to the next case.

The next branch in our case expression. Then second pattern, A cons onto B, cons

onto C, cons onto empty list, would match all lists with exactly three elements.

Matching A to the first ONP to the second and C to the third.

If the list is too short, then just like in the previous example, we'll have some

empty list value that fails to match. If the list is too long, we'll end up in

the recursive position where we have the empty list pattern trying to match

against a non empty list value, and that will fail to match.

And then in this third example, we have some more nested patterns, where we have

a cons constructor pattern with a variable on the right, that's that

variable e, and then on the left we have the sort of pattern that requires a pair

of two nested pairs. So this will only match against a

non-empty list whose elements are pairs of pairs.

And then we'll introduce five variable binates.

So, that is our more precise definition. Hopefully it gives you the sense that

pattern matching is not a fuzzy concept, it's a very precise concept.

And that better explains, that more completely explains examples we saw in

previous segments.