1 00:00:06,150 --> 00:00:09,336 In this third video, on designing an abstract function from two or more 2 00:00:09,336 --> 00:00:12,792 examples of highly repetitive code we're going to work on the signatures of the 3 00:00:12,792 --> 00:00:17,375 abstract functions. The signatures come last because with 4 00:00:17,375 --> 00:00:21,110 abstract functions. They can sometimes be the hardest thing 5 00:00:21,110 --> 00:00:25,337 to do. In order to learn how to write these 6 00:00:25,337 --> 00:00:29,369 signatures, we're first going to have to learn a couple more pieces of notation 7 00:00:29,369 --> 00:00:35,150 that we can use in type comments and signatures for describing them. 8 00:00:35,150 --> 00:00:39,862 So here we go, I'm in parameterization V3.racket and what I need to do now is 9 00:00:39,862 --> 00:00:45,658 finish up the signature for the abstract function contains. 10 00:00:45,658 --> 00:00:50,370 Remember we're abstracting a function from two or more examples of highly 11 00:00:50,370 --> 00:00:54,970 repeptiive code. I can't say that 3 times fast. 12 00:00:54,970 --> 00:00:58,813 And doing that requires us to work backwards through the htdf recipe so it's 13 00:00:58,813 --> 00:01:02,562 time to do the signature. And the way I'm going to do the signature 14 00:01:02,562 --> 00:01:05,730 here is a little bit different than the way we've done it before. 15 00:01:05,730 --> 00:01:08,963 What I'm going to do is I'm going to look at the code and read the signature off of 16 00:01:08,963 --> 00:01:11,909 it. Some programming languages do a thing 17 00:01:11,909 --> 00:01:16,130 like this automatically and it's called type inference. 18 00:01:16,130 --> 00:01:21,200 So here's how it's going to work. The first thing I do, is I look at the 19 00:01:21,200 --> 00:01:25,816 function and I see that. Let's see, there's two arguments, and of 20 00:01:25,816 --> 00:01:30,550 course every function always produces one result. 21 00:01:30,550 --> 00:01:32,870 So there's an error. What do I know about these two arguments? 22 00:01:35,230 --> 00:01:37,772 What I'll do is I'll put a placeholder there to remind me that there's two of 23 00:01:37,772 --> 00:01:41,492 them. [SOUND] And what do I know about these 24 00:01:41,492 --> 00:01:46,075 three positions? What can I write here? 25 00:01:46,075 --> 00:01:48,800 Well when we do this kind of type inference. 26 00:01:48,800 --> 00:01:52,830 We look at the function and we start with this sort of clear thing we can find. 27 00:01:52,830 --> 00:01:56,280 The most unambiguous information about the type of something we can find. 28 00:01:56,280 --> 00:02:01,150 And when I look at this function I see that in it's base case it produces false. 29 00:02:02,220 --> 00:02:05,925 And here it produces true so it's immediately clear to me what type of 30 00:02:05,925 --> 00:02:11,320 value this function produces. It produces a Boolean. 31 00:02:11,320 --> 00:02:15,264 So I can just put Boolean there. I read that because remember there's a 32 00:02:15,264 --> 00:02:19,203 false there and a true there. This function is producing false and 33 00:02:19,203 --> 00:02:25,910 true, it's therefore producing Boolean. Okay, let's keep going. 34 00:02:25,910 --> 00:02:31,009 Let's look at this first Parameter S. What happens to it. 35 00:02:31,009 --> 00:02:35,540 Well let's see. Here S is passed in the recursion, so 36 00:02:35,540 --> 00:02:40,090 that doesn't really tell me anything particularly about it's type. 37 00:02:40,090 --> 00:02:44,265 But look here. Here S is passed as an argument to string 38 00:02:44,265 --> 00:02:48,802 equals. And string equals needs both of its 39 00:02:48,802 --> 00:02:53,920 arguments to be a string. Therefore, s has to be a string. 40 00:02:53,920 --> 00:02:57,092 So I know that the type of the first argument to contains question mark, is 41 00:02:57,092 --> 00:03:02,330 string. Again, let me say how I discovered that. 42 00:03:02,330 --> 00:03:08,186 I see that the first argument to contains s Is used as an argument to string 43 00:03:08,186 --> 00:03:13,038 equals. I know that string equals require both of 44 00:03:13,038 --> 00:03:16,590 its arguments to be strings therefore s has to be a string. 45 00:03:16,590 --> 00:03:20,920 So I could put string up here as the type of the first argument to contains. 46 00:03:22,110 --> 00:03:27,263 That just leaves me with this argument. Let's see what happens with that 47 00:03:27,263 --> 00:03:31,620 argument. Well here I take first and rest of it. 48 00:03:33,860 --> 00:03:37,337 So I know its a list and I'm going to give you a new present here that we can 49 00:03:37,337 --> 00:03:42,099 use in terms of writing types. Which is instead of defining list types 50 00:03:42,099 --> 00:03:45,612 and writing list types the way we've always written them. 51 00:03:45,612 --> 00:03:49,904 I'm going to let you just write list of and then something here and that's 52 00:03:49,904 --> 00:03:54,961 going to mean a list of that. Let me keep going and I'll come back to 53 00:03:54,961 --> 00:03:59,235 this list of thing. If I look here in more detail when I take 54 00:03:59,235 --> 00:04:08,020 first of the list, first of the list ends up being an argument to string equals. 55 00:04:09,160 --> 00:04:13,128 That means first of the list has to be a string because string equals wants its 56 00:04:13,128 --> 00:04:19,044 arguments to all be strings. So this here, this first and rest told me 57 00:04:19,044 --> 00:04:22,988 that los had to be a list, and the fact that this first of los is used as an 58 00:04:22,988 --> 00:04:29,142 argument to string equals. Tells me that it has to be a list of 59 00:04:29,142 --> 00:04:35,200 string. So I can write this like that. 60 00:04:35,200 --> 00:04:38,970 And again just to explain this list of string notation, what you're allowed to 61 00:04:38,970 --> 00:04:42,566 do from now on in the course is any time you want to have a list of type, list of 62 00:04:42,566 --> 00:04:46,220 string, list of boolean, list of drop, list of whatever you want to make it be 63 00:04:46,220 --> 00:04:49,874 Instead of having to define the whole type the way we've been doing with form 64 00:04:49,874 --> 00:04:53,528 data definition, something like this, from now on you don't have to have the 65 00:04:53,528 --> 00:05:01,469 data definition. You can just write open paren list of and 66 00:05:01,469 --> 00:05:05,890 then the type of the elements of the list and a close paren. 67 00:05:07,340 --> 00:05:11,890 So that's a little present here in the middle of how we produce the signature of 68 00:05:11,890 --> 00:05:18,394 abstract functions. So there's the signature of contains. 69 00:05:18,394 --> 00:05:22,654 Let's go on and do the signature of map 2. 70 00:05:22,654 --> 00:05:24,550 It's going to work the same way. Let's see. 71 00:05:24,550 --> 00:05:33,492 Map 2 clearly consumes 2 arguments. And it produces a result. 72 00:05:33,492 --> 00:05:40,616 What do I know about those arguments? Well let's see, this first argument fun, 73 00:05:40,616 --> 00:05:45,650 is a function because right here I'm using it as a function name. 74 00:05:45,650 --> 00:05:49,777 So fun better be a function. So how are we going to write the type of 75 00:05:49,777 --> 00:05:53,810 a function? When it appears in the signature of a 76 00:05:53,810 --> 00:05:58,160 higher order function. Well the way we're going to like do it is 77 00:05:58,160 --> 00:06:02,093 like this we're going to put an open paren and then we're going to put we're 78 00:06:02,093 --> 00:06:08,150 just going to use a paren to wrap itself. We're just going to use parenthesis to 79 00:06:08,150 --> 00:06:12,110 wrap themselves around the signature of the function. 80 00:06:12,110 --> 00:06:17,594 So this part here. Will be the signature of fun because its 81 00:06:17,594 --> 00:06:23,856 the type of the first argument to map2. This'll be the type of the second 82 00:06:23,856 --> 00:06:28,010 argument to map2 and after the error will be what map2 produces. 83 00:06:31,670 --> 00:06:36,630 Okay what else can we tell from here easily. 84 00:06:36,630 --> 00:06:41,404 Well in the base case this function produces empty and in the non-base case 85 00:06:41,404 --> 00:06:46,770 it produces cons of something in the natural recursion. 86 00:06:46,770 --> 00:06:57,314 So this function is clearly producing a list so we can write list of there. 87 00:06:59,980 --> 00:07:02,090 Well, what do we know about the elements of the list? 88 00:07:04,240 --> 00:07:06,270 What can we find out about this parameter? 89 00:07:08,190 --> 00:07:12,964 Well, here we see that this function is taking the first and the rest of It's 90 00:07:12,964 --> 00:07:19,662 second argument, lon. So that means this thing is a list, too. 91 00:07:19,662 --> 00:07:23,407 [SOUND]. Notice I'm gradually building up more and 92 00:07:23,407 --> 00:07:30,330 more knowledge about the signature of the cleat function. 93 00:07:30,330 --> 00:07:33,046 Now, I want to stress here. There's no single right order to go 94 00:07:33,046 --> 00:07:36,287 through these. Okay, I kind of tend to go from the 95 00:07:36,287 --> 00:07:40,923 easiest pieces of information I can pick up about the type to the ones that 96 00:07:40,923 --> 00:07:46,026 require more work. There's different orders you could go 97 00:07:46,026 --> 00:07:48,676 through this. What matters is that you end up with the 98 00:07:48,676 --> 00:07:50,929 right signature for the abstract function. 99 00:07:52,230 --> 00:07:54,721 Okay. So what I know about the elements of this 100 00:07:54,721 --> 00:07:58,020 list. The list which is passed to map two. 101 00:07:58,020 --> 00:08:03,062 Well, to figure that out. I should look for a place that calls 102 00:08:03,062 --> 00:08:06,525 first on the list. And the only place that calls first on 103 00:08:06,525 --> 00:08:11,486 the list is right here. And notice something very interesting, 104 00:08:11,486 --> 00:08:15,936 which is. That first is past immediately to the 105 00:08:15,936 --> 00:08:21,228 function argument to map two. So map two itself never sees the first of 106 00:08:21,228 --> 00:08:24,558 the list. It doesn't really know what it's going to 107 00:08:24,558 --> 00:08:29,568 be at all. What it does know is that whatever type 108 00:08:29,568 --> 00:08:35,490 of thing first is, whatever the type of the elements of the list Is is the same 109 00:08:35,490 --> 00:08:42,130 type that function better be able to accept. 110 00:08:42,130 --> 00:08:46,554 So we've got an interesting thing. This the elements of the list as far as 111 00:08:46,554 --> 00:08:50,514 map two is concernered can be anything but they have to be something that 112 00:08:50,514 --> 00:08:56,087 function is prepared to accept. And so I'm going to introduce a new 113 00:08:56,087 --> 00:08:59,570 notation that'll allow us to express that. 114 00:08:59,570 --> 00:09:02,620 And what we're going to do is say well, you know, the type of the elements in 115 00:09:02,620 --> 00:09:08,100 this list can be anything so we're going to use whats called a type parameter. 116 00:09:08,100 --> 00:09:13,062 And by convention type parameters. Or upper case single letters of the 117 00:09:13,062 --> 00:09:17,152 alphabet. So here, we're saying, you know, the list 118 00:09:17,152 --> 00:09:25,050 can be of any type, call it x, but fn has to prepared to consume that same type x. 119 00:09:25,050 --> 00:09:29,860 So what these two 2 xs mean is they mean anything you want, as long as they're the 120 00:09:29,860 --> 00:09:30,156 same 121 00:09:30,156 --> 00:09:32,510 [INAUDIBLE]. 122 00:09:32,510 --> 00:09:34,650 Now, let's look at the type of the result list. 123 00:09:36,130 --> 00:09:39,562 Well, there, we need to look at where the elements are put in the list, and that's 124 00:09:39,562 --> 00:09:42,840 where the cons. There's only one cons in here that builds 125 00:09:42,840 --> 00:09:46,490 up the result. And look at what it's doing. 126 00:09:46,490 --> 00:09:51,490 It's taking whatever the function produces, and sticking it in the list. 127 00:09:51,490 --> 00:09:55,820 Map two itself never really operates on what the function produces. 128 00:09:55,820 --> 00:09:57,710 It just sticks it in the list without looking at it. 129 00:09:57,710 --> 00:10:02,773 So, that means that whenever function produces is going to be the type of the 130 00:10:02,773 --> 00:10:08,390 elements of the list. And we're going to use the same trick 131 00:10:08,390 --> 00:10:10,204 here. Is we're going to say the function can 132 00:10:10,204 --> 00:10:15,254 produce whatever it wants. I'll call it Y, but that's what map two 133 00:10:15,254 --> 00:10:21,470 is putting in the result list. Why? 134 00:10:21,470 --> 00:10:25,420 So let me read that from scratch. What it says, it says hey. 135 00:10:25,420 --> 00:10:30,060 The signature map to is this. Give it a function that consumes x and 136 00:10:30,060 --> 00:10:35,580 produces y. Give it a list of x and it will give you 137 00:10:35,580 --> 00:10:41,090 a list of y. So in the case of square you got a 138 00:10:41,090 --> 00:10:44,500 function from number to number and a list of number and you get back a list of 139 00:10:44,500 --> 00:10:49,960 number. The map2 can do other things. 140 00:10:52,200 --> 00:10:56,040 Why don't you right now assure yourself that map2 can do other things by doing 141 00:10:56,040 --> 00:10:59,940 this little problem where I just want you to write a check except for map2 where 142 00:10:59,940 --> 00:11:05,270 the function argument you pass to map2 is string length. 143 00:11:06,690 --> 00:11:12,932 So write that check expect now. Okay here is the check expect that I 144 00:11:12,932 --> 00:11:16,139 wrote. I said check expect remember I had 145 00:11:16,139 --> 00:11:22,810 prescribed that the function argument had to be string length. 146 00:11:22,810 --> 00:11:25,480 Well that is a function from string to natural. 147 00:11:28,060 --> 00:11:31,760 So that means x has to be string. And y is going to be natural. 148 00:11:33,650 --> 00:11:37,370 So that means the list argument to map 2 has to be a list of string. 149 00:11:37,370 --> 00:11:40,280 [SOUND]. A, b, c, d, e, f, for example. 150 00:11:40,280 --> 00:11:46,764 And what we get back is a list of the string lengths. 151 00:11:46,764 --> 00:11:52,290 List 1, 2, 3. Let check that to see if works. 152 00:11:52,290 --> 00:11:57,475 Great, now just a quick review so far we've introduced three new pieces of 153 00:11:57,475 --> 00:12:02,648 notation. You can write open prin list of followed 154 00:12:02,648 --> 00:12:06,825 by any type and a closed prin and that means a list of that type. 155 00:12:06,825 --> 00:12:11,113 In a function signature if you have to include the signature of a function you 156 00:12:11,113 --> 00:12:15,870 just put parentheses around that function signature, and I've also introduced this 157 00:12:15,870 --> 00:12:20,359 notion of type parameter which allows you to express these kinds of consistency 158 00:12:20,359 --> 00:12:24,982 relationships in signatures where you're saying for example in the case of map two 159 00:12:24,982 --> 00:12:30,658 You know? This function can consume anything it 160 00:12:30,658 --> 00:12:32,950 wants. But whatever it consumes, you better give 161 00:12:32,950 --> 00:12:40,240 me a list of that same thing. Let's do one more. 162 00:12:42,020 --> 00:12:45,390 Here's filter two that we started on. So, let's see. 163 00:12:45,390 --> 00:12:51,076 It consumes two arguments. So the signature starts out looking like 164 00:12:51,076 --> 00:12:59,340 this. And what do we know. 165 00:12:59,340 --> 00:13:03,828 Well let's look at the result position it produces empty sometimes and cons other 166 00:13:03,828 --> 00:13:08,843 times so therefore the thing its producing is clearly a list. 167 00:13:11,420 --> 00:13:17,908 List of something, we do know quite what. Let's see, let's look at it's long 168 00:13:17,908 --> 00:13:21,053 argument. Hm, here we take the first of lon, here 169 00:13:21,053 --> 00:13:24,533 we take the first lon, and here we take the rest of lon, and here we take the 170 00:13:24,533 --> 00:13:28,220 rest of lon. Lon is pretty clearly a list. 171 00:13:30,020 --> 00:13:38,000 So it's a list of something. What about pred? 172 00:13:38,000 --> 00:13:41,720 Well here, we passed pred in the natural recursion, so that doesn't tell us 173 00:13:41,720 --> 00:13:47,159 anything about its type, but here, we call pred as a one argument function. 174 00:13:49,020 --> 00:13:52,360 So pred is clearly a one argument function. 175 00:13:52,360 --> 00:13:54,160 So we'll write this. [SOUND]. 176 00:13:54,160 --> 00:14:05,440 Okay, let's keep looking at pred, since we're right there. 177 00:14:06,650 --> 00:14:11,020 Oh this is interesting. Notice that pred is used in the question 178 00:14:11,020 --> 00:14:15,987 expression part of an if. Because this call to pred appears as the 179 00:14:15,987 --> 00:14:19,320 question of an if what does pred have to return. 180 00:14:19,320 --> 00:14:26,016 It has to return a Boolean right. If wants it's question to produce either 181 00:14:26,016 --> 00:14:34,990 true or false. So this is telling us that pred has to 182 00:14:34,990 --> 00:14:46,330 produce a Boolean. Okay, let's look at the argument to pred. 183 00:14:46,330 --> 00:14:49,659 I see, the argument to pred is an element to the list. 184 00:14:50,780 --> 00:14:52,890 So that's telling us that, that, you know? 185 00:14:52,890 --> 00:14:56,350 This position and this position are going to be the same. 186 00:14:56,350 --> 00:14:58,680 Do we know anything more specific about that position? 187 00:14:58,680 --> 00:15:01,900 Let's go look. Let's see. 188 00:15:01,900 --> 00:15:05,430 Here, we call first of lon, it goes directly to pred. 189 00:15:05,430 --> 00:15:08,340 So that doesn't tell us anything more specific. 190 00:15:08,340 --> 00:15:12,240 It doesn't really look like filter two itself ever looks at the elements of the 191 00:15:12,240 --> 00:15:17,235 list. Here it passes it to pred, here it sticks 192 00:15:17,235 --> 00:15:22,102 it in the result list. Filter two never itself operates with 193 00:15:22,102 --> 00:15:27,690 some other primitive. On the elements of the list. 194 00:15:27,690 --> 00:15:33,921 So what that's saying is the elements of the list can be anything except that pred 195 00:15:33,921 --> 00:15:40,149 has to be prepared to consume them as its arguing. 196 00:15:40,149 --> 00:15:45,627 That's what this is saying here is its saying Whatever first lon produces, pred 197 00:15:45,627 --> 00:15:50,236 must be able to consume. Now we've only got one thing left which 198 00:15:50,236 --> 00:15:52,620 is the type of the elements of the result list. 199 00:15:55,550 --> 00:15:59,034 Well, this cons is the only place were we add elements to the results list, here we 200 00:15:59,034 --> 00:16:03,150 just produce empty, here we add elements to the results list. 201 00:16:03,150 --> 00:16:04,889 What do we know about the types of these elements? 202 00:16:06,390 --> 00:16:10,544 Oh, look the only thing that ever gets put in the result list is an element of 203 00:16:10,544 --> 00:16:18,513 the consumed list. What that's saying is you know whatever 204 00:16:18,513 --> 00:16:24,745 comes in is the same type that goes out. So that means that this is also x. 205 00:16:24,745 --> 00:16:33,090 If you call filter two with a list of numbers you get back a list of numbers. 206 00:16:34,610 --> 00:16:37,472 If you call filter two with a list of images you get back a list of image. 207 00:16:37,472 --> 00:16:42,477 If you call filter two with list of string you get back a list of string. 208 00:16:42,477 --> 00:16:46,829 So there you go that's the process of inferring the signature for an abstract 209 00:16:46,829 --> 00:16:51,113 function by looking at the code for the abstract function and piece by piece 210 00:16:51,113 --> 00:16:55,533 inferring what you can about the types of the arguments the abstract function 211 00:16:55,533 --> 00:17:00,988 consumes. And the type of the result the abstract 212 00:17:00,988 --> 00:17:05,824 function produces. In using tight parameters, these x's and 213 00:17:05,824 --> 00:17:10,384 y's, in places where the abstract function is willing to consume data of 214 00:17:10,384 --> 00:17:14,944 any type, but using x and y repeatedly in a single signature to talk about 215 00:17:14,944 --> 00:17:23,202 constraints where the abstract function is willing to consume any type. 216 00:17:23,202 --> 00:17:28,730 But the type of two different parts of its signature must be consistent.