1 00:00:06,220 --> 00:00:09,622 In this video, we're going to start a big function design problem that's going to 2 00:00:09,622 --> 00:00:13,078 last through several videos and it will lead us eventually to designing five 3 00:00:13,078 --> 00:00:17,945 functions. That's not at all unusual. 4 00:00:17,945 --> 00:00:22,080 In some function design problems you design many more functions than that. 5 00:00:23,450 --> 00:00:27,171 Imagine, for example, designing a function that consumes a location and 6 00:00:27,171 --> 00:00:31,380 drives a car from its current position to that location. 7 00:00:32,480 --> 00:00:35,208 I think you could easily imagine that, that would involve many, many, many 8 00:00:35,208 --> 00:00:39,366 functions. The one we're going to do now though, 9 00:00:39,366 --> 00:00:42,455 starts with one function, and we'll end up designing five. 10 00:00:42,455 --> 00:00:45,989 The basic problem is, we have a bunch of pictures or images, that we want to be 11 00:00:45,989 --> 00:00:49,470 able to store and present in different ways. 12 00:00:51,020 --> 00:00:53,522 This problem will do a simple version of the presentation. 13 00:00:53,522 --> 00:00:57,405 And later on, we'll set the stage for a more elaborate version. 14 00:00:57,405 --> 00:00:59,510 Okay. So there's two parts to this problem. 15 00:00:59,510 --> 00:01:02,774 First we have to design a data definition to represent an arbitrary number of 16 00:01:02,774 --> 00:01:07,640 images, and then, we'll design a function to arrange those images in a nice way. 17 00:01:07,640 --> 00:01:11,239 The video will pause here, while you go ahead and do part A, design a data 18 00:01:11,239 --> 00:01:15,619 definition to represent an arbitrary number of images. 19 00:01:17,310 --> 00:01:20,346 I strongly recommend that you take the time to do this yourself right now rather 20 00:01:20,346 --> 00:01:24,586 than just restart the video. But of course nobody's watching so you 21 00:01:24,586 --> 00:01:27,250 can just restart the video if you want to. 22 00:01:27,250 --> 00:01:37,350 Here's my solution for the list of image data definition. 23 00:01:37,350 --> 00:01:40,472 It's an ordinary self-referential data defintion of the kind we saw. 24 00:01:40,472 --> 00:01:43,799 Previously. There's two cases: the base case and the 25 00:01:43,799 --> 00:01:47,830 self-reference case. And, I've got an example of the empty 26 00:01:47,830 --> 00:01:52,656 list, as well as an example of a list that has a couple images in it. 27 00:01:52,656 --> 00:01:57,559 There's the template. This week you're allowed to not start 28 00:01:57,559 --> 00:02:00,815 including template rules used. That means you don't have to write the 29 00:02:00,815 --> 00:02:03,250 template rules used. So, I'm not going to write the template 30 00:02:03,250 --> 00:02:06,740 rules used. But as you read it I think you can go 31 00:02:06,740 --> 00:02:10,630 through the template rules used in your mind fairly quickly. 32 00:02:10,630 --> 00:02:13,685 It's a one of with two cases so there's a two case con. 33 00:02:13,685 --> 00:02:18,600 The first case is atomic distinct empty. We have the usual empty loi dot dot dot. 34 00:02:18,600 --> 00:02:23,495 And then there's a cons of a primitive type. 35 00:02:23,495 --> 00:02:27,700 Image. So we just have first loi, there's no 36 00:02:27,700 --> 00:02:32,560 call to a natural helper, and the natural recursion. 37 00:02:32,560 --> 00:02:33,809 There we go, there's that data definition. 38 00:02:36,280 --> 00:02:41,200 Now let's get on to, designing the functions. 39 00:02:41,200 --> 00:02:44,225 We'll make another part of the file called functions. 40 00:02:44,225 --> 00:02:47,987 And we're supposed to design a function called arrange images that consumes an 41 00:02:47,987 --> 00:02:51,521 arbitrary number of images, so that means it consumes list of image, and it 42 00:02:51,521 --> 00:02:55,800 produces an image. In which they're all laid out left to 43 00:02:55,800 --> 00:02:58,472 right. That's going to produce a single image, 44 00:02:58,472 --> 00:03:03,630 where all the images are laid out, left to right in increasing order of size. 45 00:03:03,630 --> 00:03:11,124 So what does it have to do? It has to, lay out images left to right, 46 00:03:11,124 --> 00:03:17,111 in increasing order of size. Okay? 47 00:03:17,111 --> 00:03:26,900 So, a good start for this function is just define, arrange images loi. 48 00:03:26,900 --> 00:03:30,668 And a good stop is black. By this point we've seen that these 49 00:03:30,668 --> 00:03:34,048 functions that produce images, often use blank both in their stub and in their 50 00:03:34,048 --> 00:03:39,748 base case. So, I am going to go ahead and make a 51 00:03:39,748 --> 00:03:47,630 constant for it, "square 0 solid," "white". 52 00:03:47,630 --> 00:03:55,032 Yeah, I got a constant I can use here in this stub/g. 53 00:03:59,700 --> 00:04:03,320 I'll run everything, my stub is well formed. 54 00:04:03,320 --> 00:04:09,950 Let's do some check expect, let's see check expect arrange images empty. 55 00:04:09,950 --> 00:04:13,610 Well if I ask you to arrange an empty list of images, then that's just going to 56 00:04:13,610 --> 00:04:15,690 prove blank. And let's see. 57 00:04:15,690 --> 00:04:25,866 We want to do one for a non-empty list. It should be at least two long. 58 00:04:25,866 --> 00:04:31,093 Let's see, we need to arrange images. And what I'm going to do is, I'm going to 59 00:04:31,093 --> 00:04:36,304 use the same list that I define up above. But I'm not going to refer to it as a 60 00:04:36,304 --> 00:04:38,891 constant. And I'll tell you why I'm going to do 61 00:04:38,891 --> 00:04:42,244 that. Which is, it's going to make it easier 62 00:04:42,244 --> 00:04:47,662 for me to understand my Check Expect as an example, if I actually include the 63 00:04:47,662 --> 00:04:53,789 full calls to rectangle here. 'Cuz I really understand what I'm seeing. 64 00:04:55,180 --> 00:04:58,204 So now let's see if I need to arrange those images left to right in increasing 65 00:04:58,204 --> 00:05:01,958 order of size. Well, the area of this image is 200, and 66 00:05:01,958 --> 00:05:08,270 the area of this image is 600, so they already are in increasing order of size. 67 00:05:08,270 --> 00:05:18,888 So I think this is going to be the side of this rectangle, then this rectangle. 68 00:05:18,888 --> 00:05:26,484 And also blank. Now you might ask, why are you putting 69 00:05:26,484 --> 00:05:28,840 the blank there? If the blank is blank. 70 00:05:28,840 --> 00:05:32,285 In other words, it's nothing that you see, then it doesn't really make sense to 71 00:05:32,285 --> 00:05:35,130 put it there. Because it's blank. 72 00:05:36,620 --> 00:05:39,440 Well, that's true. But the reason I'm putting the blank 73 00:05:39,440 --> 00:05:45,640 there, is remember, check-expects are examples before they are tests. 74 00:05:45,640 --> 00:05:49,980 And by putting the blank there, I'm kind of reminding myself, you know, what 75 00:05:49,980 --> 00:05:56,860 gets built up is the blank from the empty and then the other two images. 76 00:05:56,860 --> 00:06:00,600 That's why I'm putting the blank there. It's to make it clear to myself. 77 00:06:00,600 --> 00:06:04,870 Not just what the actual final image is. But in some sense, why it's the image 78 00:06:04,870 --> 00:06:06,718 that it is. We'll run it. 79 00:06:06,718 --> 00:06:12,507 They fail, but they're well formed. That's great. 80 00:06:12,507 --> 00:06:19,710 Now, I'm going to get the template. I'm going to put the template in. 81 00:06:19,710 --> 00:06:24,222 I'll rename it. I'll rename the natural recursion, I'll 82 00:06:24,222 --> 00:06:29,114 comment out the stub. And now, I'm going to think for a minute. 83 00:06:29,114 --> 00:06:33,510 And what I'm going to do is, I'm going to go back and reread the purpose. 84 00:06:33,510 --> 00:06:38,535 And the purpose says, lay out images left to right in increasing order of size. 85 00:06:38,535 --> 00:06:45,769 Now what is that meaning? Well, if I think about it for a minute, 86 00:06:45,769 --> 00:06:51,412 what it means is, sort images in increasing order of size and then lay 87 00:06:51,412 --> 00:06:58,790 them out left to right. Really, what I have to do to make them 88 00:06:58,790 --> 00:07:04,705 problem what is first, I have to take the entire list of images and I have to sort 89 00:07:04,705 --> 00:07:12,725 that entire list. And then, I have to lay those out left to 90 00:07:12,725 --> 00:07:18,512 right with [UNKNOWN]. I can't really go through the images one 91 00:07:18,512 --> 00:07:22,490 at a time, and sort each image and lay each image out. 92 00:07:22,490 --> 00:07:24,670 The sorting has to be done to the whole list. 93 00:07:24,670 --> 00:07:26,914 And then the laying out has to be done at the whole list. 94 00:07:26,914 --> 00:07:30,511 This is what's called a function composition problem. 95 00:07:30,511 --> 00:07:34,732 And if we go to the design recipes page, there's a special entry for function 96 00:07:34,732 --> 00:07:38,374 composition. And it says that you use function 97 00:07:38,374 --> 00:07:42,534 composition, when a function must perform two or more distinct and complete 98 00:07:42,534 --> 00:07:47,622 operations on the consumed data. For example, and then has this example 99 00:07:47,622 --> 00:07:52,670 that's convenient, a function that must sort and lay out a list of images. 100 00:07:52,670 --> 00:07:55,338 I won't read through the page now, you should do that afterwards, very 101 00:07:55,338 --> 00:07:59,820 carefully. Now, what happens in function composition 102 00:07:59,820 --> 00:08:05,520 is that we discard the entire template, and we replace it with a function 103 00:08:05,520 --> 00:08:13,598 composition, such as this one. And it's called a function composition, 104 00:08:13,598 --> 00:08:19,678 because what it says is, it says, first, sort the entire list, first call sort 105 00:08:19,678 --> 00:08:25,948 images to sort the entire list then take the result of that call layout images on 106 00:08:25,948 --> 00:08:34,118 it, to lay out the entire list. So the functions happen one after 107 00:08:34,118 --> 00:08:37,482 another, each on the output of the previous function. 108 00:08:37,482 --> 00:08:42,117 So this is a two function composition. You could also have problems that had 3 109 00:08:42,117 --> 00:08:45,678 or 4 or 5 functions. They tend to be weighted more towards the 110 00:08:45,678 --> 00:08:48,599 smaller number. This is a two function composition. 111 00:08:50,440 --> 00:08:53,862 Now of course I've wished for some functions that don't exist yet, so I 112 00:08:53,862 --> 00:09:00,830 better do wish list entries. Let's see, layout images consumes list of 113 00:09:00,830 --> 00:09:11,357 image and produces image, place images beside each other in order of lists. 114 00:09:11,357 --> 00:09:21,776 It's a wish list entry, so we'll do that and it's got to produce some image. 115 00:09:21,776 --> 00:09:28,390 So that's the wish list entry for layout-images. 116 00:09:28,390 --> 00:09:33,418 Let's look at sort-images. Well, sort-images consumes a ListOfImage 117 00:09:33,418 --> 00:09:42,432 and it produces a ListOfImage. Sort images. 118 00:09:42,432 --> 00:09:51,751 In increasing order of size. It's a wishlist entry. 119 00:09:51,751 --> 00:10:00,555 Now this is a function that produces a list, so we could put just empty as the 120 00:10:00,555 --> 00:10:06,720 stub here. What I'm going to do instead of putting 121 00:10:06,720 --> 00:10:10,180 empty is I'm going to put loi. Because I know that when the stub was 122 00:10:10,180 --> 00:10:15,920 called the loi will be a list of image. And so if I produce loi, I know I'll be 123 00:10:15,920 --> 00:10:20,233 producing a list of image. And you'll see a little bit later that 124 00:10:20,233 --> 00:10:24,460 this slightly different stub, this slightly more clever stub. 125 00:10:24,460 --> 00:10:27,476 Actually helps us in seeing how the program is coming together, so I'm 126 00:10:27,476 --> 00:10:33,477 putting that as my stub. Now that I've set up these wishlists and 127 00:10:33,477 --> 00:10:36,899 I know that this is a function composition function, there's one more 128 00:10:36,899 --> 00:10:41,030 thing I have to do. Which is I have to go back and think 129 00:10:41,030 --> 00:10:45,500 about these tests one more time, and here's why. 130 00:10:45,500 --> 00:10:49,855 If a function is a function composition function, then the tests for it have to 131 00:10:49,855 --> 00:10:54,520 make sure that it's composing the functions properly. 132 00:10:54,520 --> 00:10:57,800 They don't have to exhaustively test the individual functions. 133 00:10:57,800 --> 00:11:01,277 The tests for layout images will test layout images, and the test for sort 134 00:11:01,277 --> 00:11:06,269 images will test sort images. The test for range images have to make 135 00:11:06,269 --> 00:11:11,220 sure that a range images is calling layout images and sort images properly. 136 00:11:11,220 --> 00:11:15,642 One thing this means is that when you go to a function composition you don't need 137 00:11:15,642 --> 00:11:21,630 to test the base case. But another thing it means is that 138 00:11:21,630 --> 00:11:25,985 because this function is supposed to both sort and arrange, this test isn't good 139 00:11:25,985 --> 00:11:30,180 enough. Because a version of this function that 140 00:11:30,180 --> 00:11:34,520 just did the rendering, would work, because these are already in the right 141 00:11:34,520 --> 00:11:38,694 order. So I need a second test, I need at least 142 00:11:38,694 --> 00:11:45,370 one more test, in which I make sure I'll just swap these two rectangles around. 143 00:11:45,370 --> 00:11:51,450 And I won't swap them down here, because the point is that what Arrange Images 144 00:11:51,450 --> 00:11:59,466 need to do is call Sort Images to rearrange these in the right order. 145 00:11:59,466 --> 00:12:03,625 And then present them. So now,I feel like I've really tested 146 00:12:03,625 --> 00:12:08,290 that arrange images is doing both jobs, both the sorting and the laying out. 147 00:12:08,290 --> 00:12:10,655 At this point, you're basically done with arrange imagines. 148 00:12:10,655 --> 00:12:14,018 If you ran it, the test would run but fail, the reason they would run is 149 00:12:14,018 --> 00:12:19,179 because we have the wishlist entries. But they would fail. 150 00:12:19,179 --> 00:12:21,924 Because the wish list entries aren't doing the proper thing for either of 151 00:12:21,924 --> 00:12:24,972 these functions. So to recap this video. 152 00:12:24,972 --> 00:12:30,280 Remember, the first part of the week is about more rules for helper functions. 153 00:12:30,280 --> 00:12:35,035 More rules for when to split one function into multiple other functions. 154 00:12:35,035 --> 00:12:40,579 And in this video, what we saw, is the function composition rule which says that 155 00:12:40,579 --> 00:12:46,123 we should use a function composition when a single function must perform two or 156 00:12:46,123 --> 00:12:53,810 more complete operations on the entire consumed data. 157 00:12:53,810 --> 00:12:57,905 In this case for example, we have to sort List of images and then lay out the list 158 00:12:57,905 --> 00:13:01,290 of images. That's a function composition problem. 159 00:13:03,230 --> 00:13:06,246 So what I'm going to to do with this picture here, is I'm going to keep 160 00:13:06,246 --> 00:13:09,623 updating it through the next several videos. 161 00:13:09,623 --> 00:13:13,442 To show how we've broken the original problem of doing arrange-images down into 162 00:13:13,442 --> 00:13:17,470 multiple functions and which rule we used at each point. 163 00:13:18,550 --> 00:13:21,500 When you start to get into bigger programs, lots of programmers keep an 164 00:13:21,500 --> 00:13:24,500 actual pad of paper by their desk, to kind of keep track of where they are in 165 00:13:24,500 --> 00:13:28,647 something. The wish list entries are good for that, 166 00:13:28,647 --> 00:13:32,920 but some notes on pieces of paper like this are good for it too. 167 00:13:32,920 --> 00:13:36,140 There's also professional programming environments, like Eclipse, that can help 168 00:13:36,140 --> 00:13:40,430 you in some ways draw pictures like this. To keep track of where you are as well. 169 00:13:40,430 --> 00:13:42,870 That's something you could learn about in another course.