1 00:00:06,110 --> 00:00:09,701 In this video we're going to look at a new helper function rule, it's called the 2 00:00:09,701 --> 00:00:14,774 operating on a list rule. And as you'll see, what it says is that 3 00:00:14,774 --> 00:00:18,230 if you're coding a function and you reach a point where you need to operate on a 4 00:00:18,230 --> 00:00:21,747 list. Not just the first element of the list, 5 00:00:21,747 --> 00:00:26,390 but the whole list or at least potentially the whole list. 6 00:00:26,390 --> 00:00:28,392 Then you need a helper function to do that. 7 00:00:28,392 --> 00:00:32,132 Now I'm going to work on sort images. Let's see. 8 00:00:32,132 --> 00:00:37,630 Function operating on a list, we should do the base case first. 9 00:00:37,630 --> 00:00:42,166 So, if we're going to sort images of an empty list, well, if it's already empty, 10 00:00:42,166 --> 00:00:46,730 there's not a lot to sort, it comes back empty. 11 00:00:46,730 --> 00:00:51,280 Now, we need an example that's at least two long, and I've got some good example 12 00:00:51,280 --> 00:00:56,449 up here in arrange images, so let me just grab this one. 13 00:01:00,070 --> 00:01:02,860 Go back down here to sort images, so let's see. 14 00:01:02,860 --> 00:01:11,160 Check- expect, sort-images of this. [INAUDIBLE]. 15 00:01:11,160 --> 00:01:16,180 Get rid of that extra space there. Now if I'm asked to sort a list that's 16 00:01:16,180 --> 00:01:22,456 already sorted, I better not unsort it. This list is already sorted, so there's 17 00:01:22,456 --> 00:01:26,249 no use retyping it, that's just an opportunity to make a mistake. 18 00:01:28,670 --> 00:01:30,790 And Cmd+I fixes the indentation. And what does that say? 19 00:01:30,790 --> 00:01:33,952 That says if you get a list that's already in increasing order of size, then 20 00:01:33,952 --> 00:01:38,359 leave it in that order. And there's been this ambiguity floating 21 00:01:38,359 --> 00:01:44,220 around about what size means, and I'm going to clarify that size means area. 22 00:01:44,220 --> 00:01:47,390 Okay so that's an example where they come in already in order. 23 00:01:47,390 --> 00:01:49,800 Lets make an example where they come in out of order. 24 00:01:49,800 --> 00:01:53,750 And we can just do that by swapping these two rectangles again. 25 00:01:56,910 --> 00:01:59,790 So now they come in with the big one first and the little one second, and we 26 00:01:59,790 --> 00:02:04,170 need to confirm that what we produced the list ,Ttere in the other order. 27 00:02:04,170 --> 00:02:09,590 So that's pretty good for some examples. Save the file here. 28 00:02:09,590 --> 00:02:25,615 Now let's go get the template. We'll comment out the 29 00:02:25,615 --> 00:02:30,539 [UNKNOWN]. 30 00:02:30,539 --> 00:02:36,381 We'll rename the template. Rename the natural recursion/g. 31 00:02:36,381 --> 00:02:39,898 We'll start with the base case, that's usually the easiest. 32 00:02:39,898 --> 00:02:44,870 And this test tells me that the base case results should be empty, so that is easy. 33 00:02:44,870 --> 00:02:55,113 Now let's think about the recursion case. Sometimes the first element in the list 34 00:02:55,113 --> 00:03:00,330 goes right at the beginning of the rest of the list in the result. 35 00:03:00,330 --> 00:03:04,570 That's this case here. The first element of the consumed list 36 00:03:04,570 --> 00:03:09,600 goes at the beginning of the rest in the result. 37 00:03:09,600 --> 00:03:13,853 Sort of stays where it is. But sometimes the first thing in a list 38 00:03:13,853 --> 00:03:19,640 doesn't go at the beginning. And I guess if these lists were long, the 39 00:03:19,640 --> 00:03:24,537 first thing in the list could go somewhere, let's make another example 40 00:03:24,537 --> 00:03:30,360 here. Let's make an example where the first 41 00:03:30,360 --> 00:03:37,145 thing in the list is 30, 40, the second thing in the list is 10, 20, and the 42 00:03:37,145 --> 00:03:48,874 third thing in the list is 20, 30. That's gotta come back in the order 10, 43 00:03:48,874 --> 00:03:58,761 20; 20, 30 let me make this red so we don't get confused. 44 00:03:58,761 --> 00:04:12,132 And we'll make that one green. That's got to come back in the order 10 45 00:04:12,132 --> 00:04:23,775 20, 20 30 and then that one. So this thing, which starts out first 46 00:04:23,775 --> 00:04:29,470 ends up third. So this somehow has to go in the right 47 00:04:29,470 --> 00:04:32,380 place in the rest. And notice we don't have a rest. 48 00:04:32,380 --> 00:04:34,410 What we have is the result of a natural recursion. 49 00:04:34,410 --> 00:04:39,990 Now there's a really important point here for a function like sort. 50 00:04:39,990 --> 00:04:43,430 Remember we're supposed to trust the natural recursion. 51 00:04:43,430 --> 00:04:46,225 And we're trusting the natural recursion means is it means trusting that it's 52 00:04:46,225 --> 00:04:52,315 going to do it's job. so that means that what ever comes back 53 00:04:52,315 --> 00:04:59,330 from the natural recursion. Will be what? 54 00:04:59,330 --> 00:05:04,042 Well it'll be a list of [UNKNOWN] image. Because the signature says list of image 55 00:05:04,042 --> 00:05:10,596 Image, but what else will it be? Well it will also be sorted. 56 00:05:10,596 --> 00:05:16,510 Result of natural recursion will be sorted. 57 00:05:16,510 --> 00:05:21,310 And so that means I'll have one image in my hand and I'll have a sorted list in my 58 00:05:21,310 --> 00:05:25,366 hand. And what I need to do at that point is 59 00:05:25,366 --> 00:05:31,390 manage to stick the one image in the proper place in the sorted list. 60 00:05:33,440 --> 00:05:36,062 And what these examples are telling me is sometimes it'll go right at the beginning 61 00:05:36,062 --> 00:05:39,070 of the list, but sometimes it'll go farther down in the list. 62 00:05:41,130 --> 00:05:45,040 And in fact, because it's a list, the list could be arbitrarily long. 63 00:05:45,040 --> 00:05:49,596 And this first value that i need to stick into the natural recursion could be going 64 00:05:49,596 --> 00:05:54,394 very far down the list. We just don't know what arbitrary size 65 00:05:54,394 --> 00:05:57,804 means. So there's a helper function rule that 66 00:05:57,804 --> 00:06:01,240 says that if you need to operate arbitrary size data. 67 00:06:01,240 --> 00:06:04,768 If you are at a place where all at once you have to do an operation or arbitrary 68 00:06:04,768 --> 00:06:08,500 sized data, you have to use a function to do it. 69 00:06:08,500 --> 00:06:12,253 In fact, you have to use a recursive function to do it. 70 00:06:12,253 --> 00:06:16,197 Because you don't know how far into the data you have to go as part of the 71 00:06:16,197 --> 00:06:20,936 operation. So, that helper rule basically says, 72 00:06:20,936 --> 00:06:26,330 right here we need to call a new function, Insert, and we're going to wish 73 00:06:26,330 --> 00:06:31,590 for it. Let's wish for it right away. 74 00:06:31,590 --> 00:06:35,333 It's going to consume an image because first of loi is an image. 75 00:06:35,333 --> 00:06:42,461 And it's going to consume a list of image because the result of a natural recursion 76 00:06:42,461 --> 00:06:50,920 of sort images is a list of image. So it's going to consume an image in a 77 00:06:50,920 --> 00:06:54,330 list of image, and it's going to produce, well it has to produce whatever sort 78 00:06:54,330 --> 00:06:59,920 image it's supposed to produce. So, it has to produce a list of image, 79 00:06:59,920 --> 00:07:06,535 what does it do? Produce new list comma with image in 80 00:07:06,535 --> 00:07:14,744 proper place in list in increasing order of size. 81 00:07:14,744 --> 00:07:23,556 That's a little cumbersome lets see if I can say that better. 82 00:07:23,556 --> 00:07:29,736 Lets just say insert image in proper place in list in increasing order of 83 00:07:29,736 --> 00:07:34,578 size. And just to be clear about what I mean by 84 00:07:34,578 --> 00:07:39,080 image array, I'll give a name to the parameters right away. 85 00:07:39,080 --> 00:07:44,120 This is a stub. And the stub has to produce some list of 86 00:07:44,120 --> 00:07:50,159 it, so it will produce that. So insert image in proper place in list 87 00:07:50,159 --> 00:07:57,677 in increasing order of size. But there's one thing we've left out 88 00:07:57,677 --> 00:08:01,281 here. Which is, remember the special thing we 89 00:08:01,281 --> 00:08:05,010 knew about the result of the natural recursion? 90 00:08:05,010 --> 00:08:11,669 Which is that it was going to be sorted. So what we're going to do here is we're 91 00:08:11,669 --> 00:08:16,045 going to say. Assume LST is already sorted. 92 00:08:16,045 --> 00:08:23,125 because we need to communicate that fact from Sort Images to whoever designs 93 00:08:23,125 --> 00:08:27,157 Insert. because if the person that designs Insert 94 00:08:27,157 --> 00:08:29,990 doesn't know that, then what are they going to do? 95 00:08:29,990 --> 00:08:31,996 They're going to have to resort Sort again, and they're never going to get 96 00:08:31,996 --> 00:08:33,768 anywhere. But they're going to come back to the 97 00:08:33,768 --> 00:08:37,532 same helper rule. But now we know that the list is sorted, 98 00:08:37,532 --> 00:08:43,500 so insert has a smaller job to do then sort images. 99 00:08:43,500 --> 00:08:47,476 All it has to do is put its first argument ING in the right place in its 100 00:08:47,476 --> 00:08:53,146 already sorted the second argument LST. Let me go over this one more time, 101 00:08:53,146 --> 00:08:56,297 because there's two things that happened here. 102 00:08:56,297 --> 00:08:59,835 First we set up some examples quite ordinary and we added another example 103 00:08:59,835 --> 00:09:04,970 part way through also quite ordinary. The two main things that happen here are: 104 00:09:04,970 --> 00:09:08,805 one, we realized that the natural incursion was going to produce a sorted 105 00:09:08,805 --> 00:09:13,260 list and that was going to be an important fact. 106 00:09:13,260 --> 00:09:16,410 It meant that some of the work had already been done. 107 00:09:16,410 --> 00:09:20,106 We just made a note about that fact right here to ourselves so we wouldn't forget 108 00:09:20,106 --> 00:09:24,149 it. Then we realize that what ...needed to do 109 00:09:24,149 --> 00:09:30,610 was to put the first image in the right place in the sorted list. 110 00:09:30,610 --> 00:09:34,516 Then we invoked the operator on arbitrary-sized data rule, which says you 111 00:09:34,516 --> 00:09:39,080 must use a helper function to do that. So we invented the name of the helper 112 00:09:39,080 --> 00:09:42,820 function insert. And we made a wishlist entry for that 113 00:09:42,820 --> 00:09:48,045 helper function, and there we go. And now we could run at this point, and 114 00:09:48,045 --> 00:09:53,676 we have a lot of failing tests. We have a lot of failing tests because 115 00:09:53,676 --> 00:09:59,507 sort, sort kind of exists. Sort is done, but it's wishing for a 116 00:09:59,507 --> 00:10:04,289 function insert. An insert isn't done, we've got a stub 117 00:10:04,289 --> 00:10:08,620 for in, for insert. But right now at least, SortImages looks 118 00:10:08,620 --> 00:10:12,210 done, unless there's going to be some problem that crops up. 119 00:10:12,210 --> 00:10:16,634 Its tests are well formed and it's wishing for a function insert. 120 00:10:16,634 --> 00:10:20,174 >> Turning back to our overview diagram, we started with arrange-images 121 00:10:20,174 --> 00:10:25,452 which we split into two functions because of the function composition rule. 122 00:10:25,452 --> 00:10:30,845 Then we went and finished layout images. Sort images is done, but while we were 123 00:10:30,845 --> 00:10:35,465 doing it, the operate on arbitrary sized data rule caused us to wish for another 124 00:10:35,465 --> 00:10:41,072 sized function insert. So now arrange-images and sort-images are 125 00:10:41,072 --> 00:10:46,276 both probably done, as long as it turns out that insert works properly. 126 00:10:46,276 --> 00:10:50,229 And it turns out that there were no mistakes in arrange-images and sort 127 00:10:50,229 --> 00:10:53,840 images. So next we've got to focus on insert.