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.
