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.