0:00

In this segment, I want to start talking about nested patterns.

This is going to generalize everything we've been learning about pattern

matching, by doing a very simple thing which is letting us put patterns inside

of other patterns, and then extending our definition of pattern matching to account

for that. So it turns out that we can nest patterns

as deep as we want. Everywhere we have been putting variables

in patterns we can actually put other patterns.

This corresponds to the idea that when we're making expressions, we can always

put nested expressions anywhere we want. We don't have to write x plus y.

We can write expressions in those positions.

We're going to be able to do the same thing with patterns, and what this will

let us do is avoid hard to read case expressions that have other case

expressions inside of them, and instead, let us write something very elegant and

easy to read programs. So it turns out the full meaning of

pattern matching, is going to be a recursive definition, that's going to

take the idea of a pattern that can contain other patterns, and a value that

can contain other values, and see if the value has the same shape described by the

pattern, and if so, bind variables to the right parts.

But I think it will be easier to see several examples over the next couple

segments, before we get to that precise elegant recursive definition.

So what I want to do in this segment is show one nice example which relates to

zipping and unzipping. So to explain what zipping and unzipping

is I have written a function zip3 and its reverse, its inverse, unzip3 that work

like the following. If I call zip three with a triple of

lists, so three arguments, each of which was a list, say an a list of integers,

although this function it turns out this function is polymorphic, what I get back

is one list containing triples. So it went from three lists to one list

of triples and what it did is it put corresponding pieces together.

So in the arguments the first elements here are one, four, and seven, and in the

result the first element is a triple of one, four, and seven.

Similarly we then see two, five, and eight, and then three, six, and nine.

And unzip does the reverse, it takes a list of triples and returns

three lists. Where each list contains first all the

first positions from the tuples, then all the second positions from the tuples, and

then all the third positions from the tuples.

So by the way the reason why this is called zip and unzip is that it acts a

little bit like a zipper, like on your shirt or you know, on a bag or something,

because zip, takes these separate things and puts them next to each other and

unzip, takes something that was all together and separates it out.

I wouldn't look at your zipper too closely though.

Because when you actually zip, the teeth do not end up next to each other.

They end up adjacent, but the intuition is right.

Okay, so that's what I want these functions to

do. Let's see how we might implement them.

And to give you some contrast here let me start by showing you how we would do it

if we didn't have pattern matching. So here is one way to zip together three

lists, so it's a function using our old features, old zip three.

It takes in three arguments, L1, L2, and L3, and if they are all empty.

L1 is null, L2 is null, L3 is null. Then let's return the empty list.

L's if any of them are empty our lists don't have the same length and I'm going

to call that an error and I'll raise a run time exception I will show you in a

few segments how to raise exceptions but this is how you do it I've declared an

exception up here and I'll raise it. Otherwise I have three non-empty lists.

If I have three non-empty lists, let's create a couple out of the head of L1,

head of L2 and head of L3 and cons that onto the result of zipping tail of L1,

tail of L2 and tail of L3. Okay, so that's zipping.

I prefer pattern matching. this is pretty easy to get wrong.

you could easily miss some cases, you're getting no help from the type checker.

But if you go to use pattern matching the way you've been using it so far, it's

frankly a bit of a mess. So, here is a version that uses pattern

matching. And let's see, so let's first deal with

the case that all three lists are empty. Well I'd have to prod a match on L1 and

then if its empty see if L2 is empty and then if its empty see if L3 is empty.

And aha if I get here then all three lists are empty and so I should return

the empty list. In, in otherwise L3 is not empty but L1

and L2 are, so I should raise an exception.

Otherwise, L1 is empty but L2 is not, and I need to raise an exception.

Otherwise, L1 is not empty, so it patterns match head1 and tail1 and then

if L2 is empty then raise an exception. And you see where this is going, I, I'm

exploring all possibilities of empty and non-empty rather than the convenience up

above of and, also and or, else. So it turns out the fix for this is not

to abandon pattern matching but to use the fact that patterns can appear inside

of other patterns. So now let's look at how I like to write

zip three. Here is a nice concise function zip

three. It takes one argument, just like every

function in ml. Let's call it list triple, you can call

it anything you like. And let's pattern match on this triple of

lists. And let's consider three patterns.

The first pattern is this one. This is a pattern where I have a pattern

for a tupple with three patterns for lists inside of it.

And what this is going to match is any value that is a triple of three empty

lists. So if list triple, is all empty, then

this pattern will match, and I'll return the empty list.

Now let's look at the next pattern. This pattern also matches triples.

Here's before the first comma. Here's, after the, before the second

comma. Here's after the second comma.

Each thing in it has to be a non-empty list.

Why? Because this is a nested pattern that

matches against non-empty lists. Just like this one is, and this one is.

So the overall pattern will only match list triple if list triple,

is something that is a triple containing three non empty lists.

And if it matches I will bind six variables head one tail one head two tail

two head three and tail three. Head one, head two, and head three will

be bound to the beginning elements of the three lists.

And tail one, tail two, and tail three to the tails of the three lists.

And what I want to do over here, is the very elegant call cons with the triple

made from head one, head two, and head three, recursively call zip three with

tail one, tail two, and tail three. So here is my pattern.

If it matches, here is my expression. And it actually looks like I'm zipping it

up. Create a tuple out of head one, head two,

and head three, recursively zip three with tail one, tail two, and tail three.

Now that does not cover all the cases. I've covered the cases where everything

is empty and where the three elements are non-empty.

Here's a new kind of pattern: underscore. Underscore matches everything and doesn't

bind any variables. And it turns out for zipping and all the

other cases, I just want to raise an exception.

So if the first pattern doesn't match and the second pattern doesn't match, then I

want this third case. The typechecker warned me that I want

this case because my first two patterns don't cover all the possibilities.

So I really like writing programs like this.

zipping is one great example, there are other examples that work as well.

And for this segment let's finish up with unzipping and then I'll show you some

other examples in the next one. So in unzipping I want to take an

argument which is already a list of triples.

And I want to return three lists. So now my pattern matching is going to be

a little bit simpler. If this argument list is empty, then I

want to return three empty lists. That is how you unzip the empty list.

You return three lists all of which are empty.

Otherwise, I want to pattern match against a non empty list now we use to

just do this as something like head colon tail or x colon exes, alright.?

But what you can do is you can nest these patterns as well.

You can say, sure, I want to pattern match

the rest of the list against this tl variable, it has nothing to do with this

tail function. I'm just shadowing it with a tl variable.

But I want to match the head of the list against this eachof pattern, against this

tuple pattern. So, if this pattern matches, then a will

be the first component of the head of the list, b will be the second component of

the head of the list, and c will be the third component of the head of the list,

and tail will be bound to the rest of the list,

okay? These are the only two possibilities I

have to account for. Because any list of triples will either

match this pattern, or will match this pattern.

And the type of unzip three is going to require list to be a list of triples.

Okay, so once I've bound these four variables.

Let's look at this expression. Let us recursively call upzip three on

the tail that's going to give me back three lists.

Let's use ordinary each of pattern matching to bind those three lists to L1,

L2, and L3. And now I'm basically done, because I

have the three lists for unzipping the tail.

I have A, B, and C for the three components of the head of the list and

now I just want to return the triple expression that A cons on to L1, B cons

on to L2, C cons on the L3 and now. Using the idea of nested pattern

matching, I've in what, less than ten lines of code, written elegant and

concise, easy to read, zipping and unzipping for three lists.

This is a bit of an advanced example for nested pattern matching, but it uses all

the features that I want to show you. Then in the next segment I'll show you a

couple other situations, common idioms, where nested patterns are extremely

useful.