[SOUND] In this segment, I want to show some more examples of using nested pattern matching. So let's just do it. Let's jump over here and let's write some code. The first example I want to write is a function that I'll call non-decreasing. it's just going to take a list of integers and return a [INAUDIBLE]. And true means that, at no point in the list, do you find a number that is smaller than the number that comes before it. Alright, so if we did this our old fashioned way with simple pattern matching we might case on whether the list is empty or not. x colon onto x is prime. And the empty list, that's definitely true. You never see a decreasing situation. But in this case, I kind of need to look at the next element as well. And so you might, now do another pattern match on that tail of the list. And if that were empty, well this would be the situation, where you have a one element list. And that's also non-decreasing. Otherwise, you would add that next element of the list, and then really, the tail. And you would have to say, make sure that X is less than or equal to Y and also that, we were non-decreasing. Actually, and a common bug would be to say y is prime, that's actually wrong, you actually need x is prime, in order to make sure you're checking every position, and not just every other position. So this would work, but these nested case expressions are a little clumsy. And with nested patterns, we can express what I consider to be a more direct and elegant algorithm. So in, the empty list case is just fine. I have no problem with that. But now, let's use nested pattern matching to handle the one element case directly. So this pattern will match when x's is some head of the list, which we can match against x, and then the rest of the list matches against the empty list. So this pattern will match exactly against one element lists. So we can just write true. And then, if that does not match, now we can have another pattern, which is maybe, let's say, head cons onto neck. Get it, get it? That's the thing in the list after the head. Maybe on to rest, okay? and this pattern matches all lists that have two or more elements cause head will match the first, neck will match the second, and rest will match the rest of the list. And now we can just check that indeed head is less than or equal to neck. And also non-decreasing, neck cons onto rest, all right, something like that. And that is it. That's our whole function, and the type checker will actually make sure that our patterns are exhaustive, and indeed they are. We have a case for the empty list, a case for the one-element list, and a case for all lists that have two or more elements. All right? So that's another example of massive pattern matching that I actually rather like. one little thing we can do to clean this up. Whenever you have a variable that you're not using in the corresponding branch, you can also write underscore. That's a slightly better style. What it does, is it's just like a variable pattern, it always matches, but it doesn't actually introduce a variable. And that makes your code a little easier to read. It says to the reader of your code, that you don't actually need what's in that position, you just need that it's there. All right, so that's fine. Now let's do another example. this one's a little sillier but it shows something that I find quite common and convenient. I'm going to define a little data type for the sine of a number, so p for positive, n for negative, z for zero. And now what I want to do is write a little function, multsin, it's going to take a pair of integers. And it's going to return. So it takes two integers. It's going to return the sign of the number you would get if you multiplied those numbers together. But it's not actually going to do the multiplication. I'm going to define a little helper function here inside my function that just tells you the sign of a number. and so if you have zero then you end up with z. Otherwise, you get positive of x is greater than zero, is negative, and I'm going to use that to figure out the sign that you get when you multiply X1 and X2. Now it turns out there's in the extreme nine different cases based on the sign of X1 and the sign of X2. Three possibilities for each, three times three is nine. and if I tried to do this with nested case expressions it would get a little messy. But what if I just pattern matched on the pair, of calling sign with X1 and calling sign with X2? And now what I could do right here is simply have my nine cases. So I could have z comma z and have a case for that. I could have p comma z. I could have n comma z and so on. And I would continue that for nine cases. And it would, the code would read like a nice table of exactly what the answers should be for each combination. But we can do even let, better than that when we realize that patterns are matched in order. And so we know that if either thing is Z, the result will be Z, because if you multiply anything by zero you get zero. And so let's use these nested patterns to clean that up a bit. And let's say that if I have this first pattern. So if the sign of X1 is zero, then no matter what the sign of X2 is. So I could have a variable here like Y, or I could use underscore since I don't actually care what that sign is. And that's it. That's three of my nine cases, just handled like that. And here's another three. If the second position is z, then the entire thing is z. So I've already handled six of my nine cases. And now, in handling, the other, the remaining cases. I can use the fact that I now know neither position will be z, because I've already handled all those cases. so another possibility is if both things are positive. Then the result is positive. Another possibility is if both things are negative, then the result is positive. And there's two more cases, N comma P which would be negative, and P comma N which would be negative. And, not only do I have a nice table here, but my type checker will again check I haven't left anything out and that's pretty neat. by the way, you can do this slightly differently. You could just here at the end use a single wildcard which will match anything including a pair and say hey, in all remaining cases, the answer is negative. Now you'd better get rid of these or the type checker will complain that you have unreachable, impossible cases. and now whether this as I now have it written, is better style. Or the one where I don't have this line, and instead I have these two as better style, is really a matter of taste. The way I have it now is a little bit shorter. It kind of reads nicely, it says, otherwise the result is negative. But you are giving up a little bit of the type checkers helpfulness, because if I wrote this. The type checker will still say that this pattern match is exhaustive, but my code's now wrong, because I forgot the case of N comma N, whereas if I leave this case out and do it this way, here, the type checker will, in fact, give a warning, telling me that the N comma N case has been forgotten. In fact, lemme show you that. Use more nested patterns dot SML. And in fact, up here, it says, warning, match non-exhaustive. And then you can go and look at it, and try to puzzle out which case you forgot, okay? But nonetheless, let's just leave it as this one, since that's the shortest version and sometimes people like to see nice and short code. Let me finish up with one more much simpler example. which is just to compute the length of a list, so we've done this plenty of times, at least things very similar to it. If you have the empty list then return zero, otherwise x pull in, x is prime, one plus line of x is prime. And this is just another example even though there's not anything particularly nested or fancy here, where I would argue it's a little better style to go ahead and put this underscore here to emphasize that we don't care about the value at the head of the list, we just care that we have a non-empty list, and we do need the tail because we need to call Len recursively, with x as prime. All right, so those are examples, let me switch back to the slides very briefly here to just talk a little bit more about style and how these nested patterns lead to elegant and concise code, and give you an intuition on how to look for opportunities for nested pattern matching. And the first is to try to avoid, where convenient, nested case expressions. If instead of having nested case expressions, you can just have more branches using nested pattern matching, it often leads to simpler code. We saw that with unzip three in the previous segment, and we saw that with non decreasing in this segment. That's not to say that nested case expressions are always a bad idea. It's just a good hint to yourself to look and see if nested patterns might be a little better. Another very common idiom is to match against a couple of data types. So instead of pattern matching against one data type, and then another data type, and then another one, go ahead and match against a couple all at once. We just saw that with the malt sign example where I matched against two things of type sgn. We also saw that in the zip3 example. Where we actually matched against a triple of lists and that was in the previous segment. And finally, as a separate issue of style, I do encourage you to use wild cards instead of variables. A variable and a wild card both match against everything. The difference is the variable actually introduces a local binding for the thing it matched against. And the wild card does not. And when you don't need that corresponding data in the branch, wildcard concisely communicates that to the person reading your code. That is instant pattern matching. In the next segment, we'll take a step back, and give a more precise definition of how nested pattern matching is actually defined in ML and similar programming languages.
