1 00:00:06,140 --> 00:00:09,490 The abstract functions we've designed so far seem very useful. 2 00:00:10,560 --> 00:00:14,320 Lots of list functions feel like map two or filter two. 3 00:00:15,710 --> 00:00:19,182 In fact, map and filter are so useful that they are built in to the immediate 4 00:00:19,182 --> 00:00:23,290 student language. It provides them as what are called built 5 00:00:23,290 --> 00:00:27,196 in abstract list functions, and in fact, it provides several more built in 6 00:00:27,196 --> 00:00:32,109 abstract list functions. In this video, what I want to talk about 7 00:00:32,109 --> 00:00:35,953 is how you can use these built in abstract functions when you're coding one 8 00:00:35,953 --> 00:00:41,652 of your own functions. So we'll look at how to decide which 9 00:00:41,652 --> 00:00:45,950 built in function. Is appropriate in a given situation. 10 00:00:45,950 --> 00:00:48,180 And then how to set yourself up to use it properly. 11 00:00:49,770 --> 00:00:53,550 I'm in the using built ins starter dot racket file, and this file just starts 12 00:00:53,550 --> 00:00:57,030 out defining some useful data and functions that will let us have more 13 00:00:57,030 --> 00:01:00,930 interesting examples below And now I just want to talk about what some of these 14 00:01:00,930 --> 00:01:07,798 built in abstract functions are. You can get a list of all the built in 15 00:01:07,798 --> 00:01:11,890 abstract functions by going to the course website, going to the language page, 16 00:01:11,890 --> 00:01:15,858 which you can always select from here on the left hand side, going to the end of 17 00:01:15,858 --> 00:01:22,520 the language page, and here's a list of all the abstract functions. 18 00:01:22,520 --> 00:01:25,451 For example the third one in the list is map. 19 00:01:25,451 --> 00:01:29,743 Which was the 1st abstract function we did. 20 00:01:29,743 --> 00:01:34,878 And it's got it's signature and more than 1 line purpose, hmmm, and the header, 21 00:01:34,878 --> 00:01:41,911 which allows them to name parameters and write the purpose more concisely. 22 00:01:43,420 --> 00:01:46,465 Let's jump back over to racquet and see some of these functions in action. 23 00:01:46,465 --> 00:01:50,415 I've got some check expects here to demonstrate them. 24 00:01:50,415 --> 00:01:55,624 And what I'm going to do is run them. Now, there's going to be a couple of 25 00:01:55,624 --> 00:01:59,372 failing tests. But those are actually from farther down 26 00:01:59,372 --> 00:02:02,030 in the file. These check-expects here are working, and 27 00:02:02,030 --> 00:02:04,930 I'm actually going to also demo them down here, just to drive home what's 28 00:02:04,930 --> 00:02:08,698 happening. So I'll take this and copy it and go down 29 00:02:08,698 --> 00:02:12,976 to the Interactions area, and if I map the predicate positive Over a list of 30 00:02:12,976 --> 00:02:17,185 numbers while I get back the result of calling positive with each of those 31 00:02:17,185 --> 00:02:23,760 numbers, which in this case is true, false, true, false. 32 00:02:23,760 --> 00:02:31,582 If on the other hand I use filter with negative. 33 00:02:33,700 --> 00:02:39,480 I get only the negative numbers, minus 2 and minus 4. 34 00:02:39,480 --> 00:02:43,200 Is an abstract function we didn't abstract before but I think you'll see 35 00:02:43,200 --> 00:02:51,615 what it is pretty quickly, this is foldr. And if I call foldr with plus 0 and the 36 00:02:51,615 --> 00:02:59,730 list 1, 2, 3, I get 6. Foldr is the abstraction of sum and 37 00:02:59,730 --> 00:03:04,847 product. Plus is the combination, 0 is the base 38 00:03:04,847 --> 00:03:10,490 case result. And that's the list that it operates on. 39 00:03:10,490 --> 00:03:15,560 The way to think about it is that folder is filling in the ordinary template for 40 00:03:15,560 --> 00:03:21,616 operating on a list of x. So folder in some sense is the abstract 41 00:03:21,616 --> 00:03:27,048 function for the list of x template. And we can use it in other kinds of ways, 42 00:03:27,048 --> 00:03:34,020 for example, [SOUND] here we're doing the product function that we did before. 43 00:03:34,020 --> 00:03:37,330 Now Build List is one we haven't seen before. 44 00:03:37,330 --> 00:03:42,556 Let's jump over to its documentation. What it says about build lists is that it 45 00:03:42,556 --> 00:03:46,092 consumes a natural number, and a function which is self consumes a natural number 46 00:03:46,092 --> 00:03:51,150 and produces x. And this function produces a list of 47 00:03:51,150 --> 00:03:53,835 those x's. And what it does is it calls the 48 00:03:53,835 --> 00:04:00,425 function, it produces a list. Of calling the function on zero...all the 49 00:04:00,425 --> 00:04:05,220 way up to calling the function on minus n1. 50 00:04:05,220 --> 00:04:08,490 Let me show you that more concretely. I need to tell you first that there's 51 00:04:08,490 --> 00:04:14,140 this funny function in Racket which was made pretty much exclusively to use with. 52 00:04:14,140 --> 00:04:18,300 Build list and some other abstract functions. 53 00:04:18,300 --> 00:04:21,120 This function is called identity. And all identity does is whatever you 54 00:04:21,120 --> 00:04:23,580 give it as an argument, it gives you back. 55 00:04:23,580 --> 00:04:28,120 So it's the identity function, it produces its argument. 56 00:04:28,120 --> 00:04:34,197 If I use identity with build list Let's say I say build list of three, and 57 00:04:34,197 --> 00:04:39,885 identity. I get the list zero, one, two. 58 00:04:39,885 --> 00:04:44,942 Because look, what's it doing? It's calling identity on zero. 59 00:04:44,942 --> 00:04:50,450 It's calling identity on one. It's calling identity on two. 60 00:04:50,450 --> 00:04:53,505 And it's stopping there because two is 3 minus 1. 61 00:04:55,000 --> 00:05:00,592 And it's making a list of those results. Here's another one. 62 00:05:00,592 --> 00:05:08,150 If I say Build list square on four I'll get oops, I got the arguments backwards. 63 00:05:08,150 --> 00:05:12,339 [SOUND] Build list 4 on sqr, I get 0 which is the square of 0, 1 which is the 64 00:05:12,339 --> 00:05:18,956 square of 1, 4 which is the square of 2, and 9 which is the square of 3. 65 00:05:18,956 --> 00:05:26,370 Build-list is a funny thing we'll see why we want to use it a little bit later. 66 00:05:26,370 --> 00:05:32,065 Here's some problems that are all of the same form, they've all got the beginning 67 00:05:32,065 --> 00:05:39,370 of a function design And they're at the template code, the body stage. 68 00:05:39,370 --> 00:05:43,930 And what I'm going to show you how to do is how to recognize that this is a case 69 00:05:43,930 --> 00:05:50,380 that you could code the body by calling a built abstract function. 70 00:05:50,380 --> 00:05:54,500 The basic trick is to, first kind of get the insight, hey you know. 71 00:05:54,500 --> 00:05:58,469 This feels like it's a fairly generic operation on the list, maybe there's a 72 00:05:58,469 --> 00:06:02,755 built in abstract function, I wonder which one it is? 73 00:06:02,755 --> 00:06:05,955 But after awhile you get pretty good at doing it just kind of automatically. 74 00:06:05,955 --> 00:06:09,435 But until then the way to do it is to compare the signature of the function 75 00:06:09,435 --> 00:06:14,342 you're trying to design; here it's list of image to list of image. 76 00:06:14,342 --> 00:06:21,335 To the signatures of the built-in abstract functions, which I've got here, 77 00:06:21,335 --> 00:06:28,218 minus their function argument. So now, I'm taking away their function 78 00:06:28,218 --> 00:06:32,565 argument, and so what I'm going to do is compare a list of image, to list of image 79 00:06:32,565 --> 00:06:37,080 to these signatures. Well, it doesn't match the first one. 80 00:06:37,080 --> 00:06:39,619 It doesn't match a build list, 'cuz that can, seems natural. 81 00:06:41,510 --> 00:06:45,164 It matches both of the next two because listof image to listof image matches 82 00:06:45,164 --> 00:06:48,876 listof x to listof x, and also matches listof x to listof y cause remember x and 83 00:06:48,876 --> 00:06:54,079 y don't have to be different they just can be different. 84 00:06:56,750 --> 00:07:01,436 And it doesn't match any of the remaining ones because list of image sure as heck 85 00:07:01,436 --> 00:07:06,980 isn't boolean and the last two functions take two arguments. 86 00:07:06,980 --> 00:07:10,610 So it's either filter or map and in this case of course, it's filter because this 87 00:07:10,610 --> 00:07:15,250 if filtering behavior. We're potentially producing Fewer 88 00:07:15,250 --> 00:07:20,220 elements in the result list than in the consumed list. 89 00:07:20,220 --> 00:07:24,124 That's what filter does, map always produces 1 element in the result list for 90 00:07:24,124 --> 00:07:28,975 each element in the consumed list. So this is a filter and the way we're 91 00:07:28,975 --> 00:07:32,680 going to template it is like this, we're going to say, hey this is a filter I 92 00:07:32,680 --> 00:07:38,314 won't know what argument to pass it. Here, but I do know it gets the list 93 00:07:38,314 --> 00:07:45,270 here. Now this is the template. 94 00:07:45,270 --> 00:07:48,231 Now at this point in the course, you don't really for your own purposes, need 95 00:07:48,231 --> 00:07:51,875 to save the template, right? Templating is starting to become 96 00:07:51,875 --> 00:07:55,120 something that you understand the structure of If you can write it down 97 00:07:55,120 --> 00:07:59,890 quickly, you write it and go, or you copy if from a data definition. 98 00:07:59,890 --> 00:08:07,206 I'm going to leave it here just for your purposes so you can understand what we 99 00:08:07,206 --> 00:08:15,980 did here today in this video. Let me copy it and now comment that one 100 00:08:15,980 --> 00:08:18,700 out. And now you have to, as usual, fill in 101 00:08:18,700 --> 00:08:22,208 the dots. And the question is, what is the 102 00:08:22,208 --> 00:08:26,396 predicate that we pass to filter? Again, if I go look at the complete 103 00:08:26,396 --> 00:08:30,828 signature for filter. It's first argument is a function that 104 00:08:30,828 --> 00:08:39,470 consumes x, and produces Boolean. Its second argument is a list of x. 105 00:08:39,470 --> 00:08:43,330 And its result is a list of x. So this needs to be a predicate here. 106 00:08:43,330 --> 00:08:45,480 It needs to be a predicate that consumes x. 107 00:08:45,480 --> 00:08:49,512 Now you may not remember this because it went by quickly, but at the top of this 108 00:08:49,512 --> 00:08:54,830 file, there's a predicate called Wide Question Mark. 109 00:08:54,830 --> 00:08:59,315 Which consumes an image which is what x is in this case, and produces a boolean, 110 00:08:59,315 --> 00:09:05,614 and it produces two of the images wide. So, this is what we want. 111 00:09:05,614 --> 00:09:12,930 We'll go back down to wide only and we'll just put [SOUND] y question mark in 112 00:09:12,930 --> 00:09:17,292 there. And one of the things that's nice about 113 00:09:17,292 --> 00:09:21,100 using built in abstract functions, is that your function definitions get really 114 00:09:21,100 --> 00:09:24,088 short. And they get really short, they get so 115 00:09:24,088 --> 00:09:27,540 short that you might even be tempted to write them on one line. 116 00:09:27,540 --> 00:09:31,729 The book sometimes calls that a one-liner, but But let me note, that you 117 00:09:31,729 --> 00:09:37,130 know, what it means to be a one-liner is that it's very short. 118 00:09:37,130 --> 00:09:41,220 So that's really still, for all intents and purposes a one-liner. 119 00:09:41,220 --> 00:09:48,080 It's very short, it's very simple because we used the abstract function. 120 00:09:48,080 --> 00:09:51,260 And let me make one more point here about the benefit of using The built in 121 00:09:51,260 --> 00:09:55,450 abstract functions. It's already up here above, but you might 122 00:09:55,450 --> 00:09:59,870 not have noticed it before. Notice that I don't have a base case test 123 00:09:59,870 --> 00:10:02,801 here. And the reason I don't have a base case 124 00:10:02,801 --> 00:10:08,400 test is that the built in abstract functions are already thoroughly tested. 125 00:10:08,400 --> 00:10:12,580 I know that they're base case behavior is going to be correct. 126 00:10:12,580 --> 00:10:15,559 So I don't really need the base case test for the built in abstract function. 127 00:10:16,570 --> 00:10:19,690 So when you use one of them, you don't have to follow the normal rule about 128 00:10:19,690 --> 00:10:26,266 starting with a base case test. Let me do another one quickly. 129 00:10:26,266 --> 00:10:32,900 List of Image to Boolean are all the images in loi tall and I'm asking are all 130 00:10:32,900 --> 00:10:42,840 the images in loi one Tall. Let's go look at what l o i 1 is. 131 00:10:42,840 --> 00:10:48,760 See l o i 1 has all of these rectangles in it, so they're clearly not all tall. 132 00:10:48,760 --> 00:10:51,380 Other the other hand, let's see if I just took. 133 00:10:51,380 --> 00:10:56,914 One and three, they would all be tall. So, let me go back down there and add 134 00:10:56,914 --> 00:11:03,523 that as a second test. So, now I've improved the set up a bit, 135 00:11:03,523 --> 00:11:13,160 and the question is which built in abstract list function is this? 136 00:11:13,160 --> 00:11:18,326 Let's see, I consume A list of image, I produce a bullion, I take the abstract 137 00:11:18,326 --> 00:11:23,902 list function signatures, I remove their function argument, which one matches, 138 00:11:23,902 --> 00:11:31,582 well it's and map or, or map. And if I go to the language page and look 139 00:11:31,582 --> 00:11:40,244 at the description of and map and or map. In that, it says, produce true if p 140 00:11:40,244 --> 00:11:45,697 produces true for every element of lox whereas or is for some element of lox. 141 00:11:45,697 --> 00:11:50,596 And unsurprisingly, I probably could have done this without looking here, but since 142 00:11:50,596 --> 00:11:55,100 this purpose is are all the images in loi all-tall. 143 00:11:55,100 --> 00:11:58,898 This is going to be an and map, so I'll say define all-tall. 144 00:11:58,898 --> 00:12:01,750 loi, and map, dot, dot, dot. loi. 145 00:12:01,750 --> 00:12:07,924 And this time I'm not even going to preserve the template. 146 00:12:07,924 --> 00:12:13,510 I'll just have briefly this template stage. 147 00:12:13,510 --> 00:12:17,220 And now I have to decide what goes in the and map. 148 00:12:17,220 --> 00:12:25,320 And of course it's the predicate, tall question mark. 149 00:12:25,320 --> 00:12:27,950 Let's see. That test is passing. 150 00:12:27,950 --> 00:12:33,138 The first failing test is after that. First failing test is sum. 151 00:12:33,138 --> 00:12:38,416 I need to let you do sum as an exercise now and I want you to go through the 152 00:12:38,416 --> 00:12:44,517 whole process I've just shown. Compare the signature of sum to the 153 00:12:44,517 --> 00:12:49,493 signature of all the other functions. I'm going to give you a hint here though. 154 00:12:49,493 --> 00:12:53,471 I do want you to compare the process. This, but I am going to give you a hint 155 00:12:53,471 --> 00:12:58,580 here, which is that the function that you're looking for here is Folder. 156 00:12:58,580 --> 00:13:02,057 So go ahead and do this as an exercise, and when we come back I'll do the last 157 00:13:02,057 --> 00:13:11,430 one. So here was my solution for sum, and I 158 00:13:11,430 --> 00:13:13,950 just want to show you one little thing that you could do in the middle of it 159 00:13:13,950 --> 00:13:18,497 that might make it a bit easier. Once you figure out its folder, and you 160 00:13:18,497 --> 00:13:22,462 have the template with the two sets of dots because remember folder's going to 161 00:13:22,462 --> 00:13:26,450 need Two arguments in addition to the list. 162 00:13:26,450 --> 00:13:32,860 One thing you could do is go decorate those dots with their type. 163 00:13:34,000 --> 00:13:38,775 So since the signature of folder is y, list of x to y. 164 00:13:38,775 --> 00:13:44,480 And since we want to produce a number, that means y has to be a number. 165 00:13:44,480 --> 00:13:48,704 So that means first argument of folder, which is supposed to be a function x, y 166 00:13:48,704 --> 00:13:52,827 to y. Let's see, x we know is number, y is 167 00:13:52,827 --> 00:13:59,960 number. So, this first set of dots actually has 168 00:13:59,960 --> 00:14:06,304 to have that type. The second set of dots, the second 169 00:14:06,304 --> 00:14:10,619 argument to folder has to be a y, we know that's number now. 170 00:14:15,430 --> 00:14:19,708 So that second set of dots has to have type number and that helps you when you 171 00:14:19,708 --> 00:14:24,726 go to fill in the dots. You know that the first set of dots needs 172 00:14:24,726 --> 00:14:28,644 to be a function and with that signature, in this case, it's plus. 173 00:14:30,330 --> 00:14:33,210 [SOUND] You know that the second set of dots needs to be a number, in this case, 174 00:14:33,210 --> 00:14:36,808 zero. So that's a little thing to do for these 175 00:14:36,808 --> 00:14:42,259 more complicated ones like Folder, where These multiple arguments is you can kind 176 00:14:42,259 --> 00:14:47,631 of, once you've decided which function to use, then you know what types your Xs and 177 00:14:47,631 --> 00:14:52,450 Ys are, and you can decorate your template a little bit more with the types 178 00:14:52,450 --> 00:15:01,116 you need. Let me do this one last one, which is a 179 00:15:01,116 --> 00:15:05,526 little bit tricky. You don't have to follow it if you don't 180 00:15:05,526 --> 00:15:08,090 want to. Here's a funny one. 181 00:15:08,090 --> 00:15:11,506 I'm, I'm consuming a natural and producing a natural and I'm trying to add 182 00:15:11,506 --> 00:15:17,860 up the first n natural numbers. Hmm. 183 00:15:17,860 --> 00:15:22,350 Well, that's natural to natural. And that doesn't match any of these; 184 00:15:22,350 --> 00:15:25,940 there's only one of them that consumes the natural and it produces a list. 185 00:15:25,940 --> 00:15:28,406 That's build-list. On the other hand, there are two of them 186 00:15:28,406 --> 00:15:32,096 that are willing to produce something other than a list, foldr and foldl. 187 00:15:32,096 --> 00:15:37,810 Ignore foldl for now. Let's see, build-list will go from a 188 00:15:37,810 --> 00:15:47,544 natural to a list, and foldl will go from a list back to something else like a 189 00:15:47,544 --> 00:15:55,361 natural. So this is going to be templated as a 190 00:15:55,361 --> 00:16:04,360 composition of folder and build list. We need to do two things. 191 00:16:04,360 --> 00:16:10,248 [SOUND]. We're going to folder with a function 192 00:16:10,248 --> 00:16:15,648 argument. And some base case value, and a list. 193 00:16:15,648 --> 00:16:22,456 Where are we going to get the list? We're going to get that from build list, 194 00:16:22,456 --> 00:16:30,090 with a natural argument, in this case the original n. 195 00:16:30,090 --> 00:16:34,325 And some function. Now how do we fill them in? 196 00:16:34,325 --> 00:16:39,491 Well build-list already does produce the first n natural numbers, if we say 197 00:16:39,491 --> 00:16:44,821 build-list n and identity Let me, let me save this template so you can look at it 198 00:16:44,821 --> 00:16:57,200 as we go. We'll comment out the stub. 199 00:16:57,200 --> 00:17:02,756 We'll comment out the temapate. If we say build this with n in identity, 200 00:17:02,756 --> 00:17:05,777 that's going to give us the first n natural numbers because if we call it 201 00:17:05,777 --> 00:17:10,000 with n equals two for example, we'll get zero and one. 202 00:17:10,000 --> 00:17:15,444 The first n natural numbers. So there's a list of the first n natural 203 00:17:15,444 --> 00:17:19,452 numbers. Now, I need to add them up. 204 00:17:19,452 --> 00:17:28,062 Well that's just the old sum function plus and zero. 205 00:17:28,062 --> 00:17:36,544 So, now you see why build list is there. Build list is there because it's often 206 00:17:36,544 --> 00:17:39,830 useful to produce the list argument to folder. 207 00:17:39,830 --> 00:17:45,510 This is a way of saying let folder do something to a bunch of natural numbers. 208 00:17:46,970 --> 00:17:49,572 That's build lists role. And in fact lots of languages have 209 00:17:49,572 --> 00:17:53,255 something like this. Python has something called range, which 210 00:17:53,255 --> 00:17:58,682 works exactly this way. So there's examples of using built-in 211 00:17:58,682 --> 00:18:02,830 abstract functions and simplify the final two stages of the function recipe, the 212 00:18:02,830 --> 00:18:07,880 templating stage and the coding the details of the body stage. 213 00:18:07,880 --> 00:18:12,744 The basic idea is first you get an idea that hey this function is amenable to be 214 00:18:12,744 --> 00:18:18,640 coded as a call to a built-in abstract function. 215 00:18:18,640 --> 00:18:21,664 Then you figure out which built in abstract function it is then you template 216 00:18:21,664 --> 00:18:24,495 that way and then you work out the details. 217 00:18:24,495 --> 00:18:28,094 There's going to be a number of practice problems on this because this is the 218 00:18:28,094 --> 00:18:33,429 thing that really takes some practice. Remember a perfectly viable way to do 219 00:18:33,429 --> 00:18:38,620 this is to first code the function the old fashioned way. 220 00:18:38,620 --> 00:18:43,253 First code it out using the ordinary list template, and fill it all in. 221 00:18:43,253 --> 00:18:47,474 And then maybe once you've got that, think to yourself, well which abstract 222 00:18:47,474 --> 00:18:51,324 function is that? You don't have to jump directly to that 223 00:18:51,324 --> 00:18:55,695 abstract function if that seems too hard. Remember the basic idea of the recipe. 224 00:18:55,695 --> 00:18:59,465 The basic idea of the recipe is always write down the easiest thing you know how 225 00:18:59,465 --> 00:19:03,310 to write in that. List, and then go from there. 226 00:19:03,310 --> 00:19:07,468 So if the easiest thing you know how to write next is the old-fashioned template 227 00:19:07,468 --> 00:19:11,500 and filling it in, write that and then go from there to the call to the built-in 228 00:19:11,500 --> 00:19:16,580 abstract function. If, on the other hand, you think you can 229 00:19:16,580 --> 00:19:19,660 figure out which built-in abstract function to use, go directly to 230 00:19:19,660 --> 00:19:24,050 templating a call to that and then filling in the details.