In this video we're going to look at a new helper function rule, it's called the operating on a list rule. And as you'll see, what it says is that if you're coding a function and you reach a point where you need to operate on a list. Not just the first element of the list, but the whole list or at least potentially the whole list. Then you need a helper function to do that. Now I'm going to work on sort images. Let's see. Function operating on a list, we should do the base case first. So, if we're going to sort images of an empty list, well, if it's already empty, there's not a lot to sort, it comes back empty. Now, we need an example that's at least two long, and I've got some good example up here in arrange images, so let me just grab this one. Go back down here to sort images, so let's see. Check- expect, sort-images of this. [INAUDIBLE]. Get rid of that extra space there. Now if I'm asked to sort a list that's already sorted, I better not unsort it. This list is already sorted, so there's no use retyping it, that's just an opportunity to make a mistake. And Cmd+I fixes the indentation. And what does that say? That says if you get a list that's already in increasing order of size, then leave it in that order. And there's been this ambiguity floating around about what size means, and I'm going to clarify that size means area. Okay so that's an example where they come in already in order. Lets make an example where they come in out of order. And we can just do that by swapping these two rectangles again. So now they come in with the big one first and the little one second, and we need to confirm that what we produced the list ,Ttere in the other order. So that's pretty good for some examples. Save the file here. Now let's go get the template. We'll comment out the [UNKNOWN]. We'll rename the template. Rename the natural recursion/g. We'll start with the base case, that's usually the easiest. And this test tells me that the base case results should be empty, so that is easy. Now let's think about the recursion case. Sometimes the first element in the list goes right at the beginning of the rest of the list in the result. That's this case here. The first element of the consumed list goes at the beginning of the rest in the result. Sort of stays where it is. But sometimes the first thing in a list doesn't go at the beginning. And I guess if these lists were long, the first thing in the list could go somewhere, let's make another example here. Let's make an example where the first thing in the list is 30, 40, the second thing in the list is 10, 20, and the third thing in the list is 20, 30. That's gotta come back in the order 10, 20; 20, 30 let me make this red so we don't get confused. And we'll make that one green. That's got to come back in the order 10 20, 20 30 and then that one. So this thing, which starts out first ends up third. So this somehow has to go in the right place in the rest. And notice we don't have a rest. What we have is the result of a natural recursion. Now there's a really important point here for a function like sort. Remember we're supposed to trust the natural recursion. And we're trusting the natural recursion means is it means trusting that it's going to do it's job. so that means that what ever comes back from the natural recursion. Will be what? Well it'll be a list of [UNKNOWN] image. Because the signature says list of image Image, but what else will it be? Well it will also be sorted. Result of natural recursion will be sorted. And so that means I'll have one image in my hand and I'll have a sorted list in my hand. And what I need to do at that point is manage to stick the one image in the proper place in the sorted list. And what these examples are telling me is sometimes it'll go right at the beginning of the list, but sometimes it'll go farther down in the list. And in fact, because it's a list, the list could be arbitrarily long. And this first value that i need to stick into the natural recursion could be going very far down the list. We just don't know what arbitrary size means. So there's a helper function rule that says that if you need to operate arbitrary size data. If you are at a place where all at once you have to do an operation or arbitrary sized data, you have to use a function to do it. In fact, you have to use a recursive function to do it. Because you don't know how far into the data you have to go as part of the operation. So, that helper rule basically says, right here we need to call a new function, Insert, and we're going to wish for it. Let's wish for it right away. It's going to consume an image because first of loi is an image. And it's going to consume a list of image because the result of a natural recursion of sort images is a list of image. So it's going to consume an image in a list of image, and it's going to produce, well it has to produce whatever sort image it's supposed to produce. So, it has to produce a list of image, what does it do? Produce new list comma with image in proper place in list in increasing order of size. That's a little cumbersome lets see if I can say that better. Lets just say insert image in proper place in list in increasing order of size. And just to be clear about what I mean by image array, I'll give a name to the parameters right away. This is a stub. And the stub has to produce some list of it, so it will produce that. So insert image in proper place in list in increasing order of size. But there's one thing we've left out here. Which is, remember the special thing we knew about the result of the natural recursion? Which is that it was going to be sorted. So what we're going to do here is we're going to say. Assume LST is already sorted. because we need to communicate that fact from Sort Images to whoever designs Insert. because if the person that designs Insert doesn't know that, then what are they going to do? They're going to have to resort Sort again, and they're never going to get anywhere. But they're going to come back to the same helper rule. But now we know that the list is sorted, so insert has a smaller job to do then sort images. All it has to do is put its first argument ING in the right place in its already sorted the second argument LST. Let me go over this one more time, because there's two things that happened here. First we set up some examples quite ordinary and we added another example part way through also quite ordinary. The two main things that happen here are: one, we realized that the natural incursion was going to produce a sorted list and that was going to be an important fact. It meant that some of the work had already been done. We just made a note about that fact right here to ourselves so we wouldn't forget it. Then we realize that what ...needed to do was to put the first image in the right place in the sorted list. Then we invoked the operator on arbitrary-sized data rule, which says you must use a helper function to do that. So we invented the name of the helper function insert. And we made a wishlist entry for that helper function, and there we go. And now we could run at this point, and we have a lot of failing tests. We have a lot of failing tests because sort, sort kind of exists. Sort is done, but it's wishing for a function insert. An insert isn't done, we've got a stub for in, for insert. But right now at least, SortImages looks done, unless there's going to be some problem that crops up. Its tests are well formed and it's wishing for a function insert. >> Turning back to our overview diagram, we started with arrange-images which we split into two functions because of the function composition rule. Then we went and finished layout images. Sort images is done, but while we were doing it, the operate on arbitrary sized data rule caused us to wish for another sized function insert. So now arrange-images and sort-images are both probably done, as long as it turns out that insert works properly. And it turns out that there were no mistakes in arrange-images and sort images. So next we've got to focus on insert.