0:00

[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.