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.
