1 00:00:06,120 --> 00:00:09,800 So the last two videos, we saw some pretty amazing stuff. 2 00:00:10,900 --> 00:00:14,869 We had a type comment that referred to itself, and then we have function that 3 00:00:14,869 --> 00:00:19,268 called itself. And that function actually did what we 4 00:00:19,268 --> 00:00:22,480 wanted it to do. Instead of just going around and around 5 00:00:22,480 --> 00:00:29,450 in circles, on and on and on forever. Now, why is that? 6 00:00:29,450 --> 00:00:31,210 That's what I'm going to talk about in this video. 7 00:00:32,260 --> 00:00:34,770 There's some pretty deep computer science underlying all of this. 8 00:00:34,770 --> 00:00:38,700 And we're not going to get into it, in, in kind of, more academic terms. 9 00:00:38,700 --> 00:00:44,570 But what we will see is that the type comment has two key properties. 10 00:00:46,150 --> 00:00:50,030 And the way we derive the template preserves those properties. 11 00:00:50,030 --> 00:00:54,422 So that we end up with functions that work properly, even though they call 12 00:00:54,422 --> 00:00:58,128 themselves. So what I'm going to do is explain that., 13 00:00:58,128 --> 00:01:01,133 make a few additions to the design recipes. 14 00:01:01,133 --> 00:01:04,787 So that you can keeping doing that systematically and producing recursive 15 00:01:04,787 --> 00:01:11,370 functions that work properly on your own. This file is quidditch recap starter. 16 00:01:11,370 --> 00:01:15,524 It's basically just the solutions from the last video rearranged slightly so so 17 00:01:15,524 --> 00:01:19,420 that I had both parts of the problem in one box. 18 00:01:19,420 --> 00:01:22,238 That gives me some room below. The first thing I want to know is right 19 00:01:22,238 --> 00:01:27,074 here in the Problem description. Notice that we're designing a program 20 00:01:27,074 --> 00:01:30,583 that will keep track of your favorite quidditch teams. 21 00:01:30,583 --> 00:01:33,650 Now, ask yourself, how many teams are there? 22 00:01:33,650 --> 00:01:37,072 We don't know ahead of time. It could be one, it could be two, there 23 00:01:37,072 --> 00:01:41,890 could be three, there could be 60, we just don't know ahead of time. 24 00:01:41,890 --> 00:01:46,320 This is what we call, arbitrary sized. Arbitrary doesn't means random, it just 25 00:01:46,320 --> 00:01:50,077 means we don't know ahead of time. Time now whenever we have an arbitrary 26 00:01:50,077 --> 00:01:54,806 size data problem whenever we need data to be of arbitrary size. 27 00:01:54,806 --> 00:01:58,436 What we're going to see is that we want to use self reference in the type 28 00:01:58,436 --> 00:02:01,684 comment. This type comment has the self reference 29 00:02:01,684 --> 00:02:06,220 in it as we noted before. And we saw how that made it possible for 30 00:02:06,220 --> 00:02:11,393 it to account for lists of any size. We just make one more cycle around the 31 00:02:11,393 --> 00:02:14,910 self-reference relationship for each element of the list. 32 00:02:14,910 --> 00:02:17,120 But why does this self-reference work out? 33 00:02:17,120 --> 00:02:20,454 Why doesn't it in some sense blow up? Because it just keeps going around. 34 00:02:20,454 --> 00:02:25,074 Well, the key thing is that this is called a well formed self referential 35 00:02:25,074 --> 00:02:29,443 data definition. And it's well formed because it has the 36 00:02:29,443 --> 00:02:34,666 self reference case, that's true, that's what lets it get longer and longer. 37 00:02:34,666 --> 00:02:40,307 But it also has the non self referential case, or the base case. 38 00:02:40,307 --> 00:02:45,270 And that's what lets it stop. So in a well formed self referential data 39 00:02:45,270 --> 00:02:49,890 definition, you always have both the base case that has no self reference, and a 40 00:02:49,890 --> 00:02:55,238 self reference case. Now, this is a simple self referential 41 00:02:55,238 --> 00:02:58,930 data definition. It's possible for these type comments to 42 00:02:58,930 --> 00:03:03,480 have more than one self reference case, and more than one base case. 43 00:03:03,480 --> 00:03:07,696 The rule for being well formed is that there has to be at least one base case, 44 00:03:07,696 --> 00:03:14,320 non self referential case. And at least one self referential case. 45 00:03:14,320 --> 00:03:18,214 So the summary so far is, if you have an arbitrary amount of information you need 46 00:03:18,214 --> 00:03:21,480 to represent. You need to use a well formed self 47 00:03:21,480 --> 00:03:24,760 referential data definition, that gets us to here. 48 00:03:24,760 --> 00:03:29,170 And if we look at the how to design data page what we've got so far is reflected 49 00:03:29,170 --> 00:03:35,018 here. And the choice of what form of data 50 00:03:35,018 --> 00:03:39,010 definition to use. When information to be represented is of 51 00:03:39,010 --> 00:03:43,610 arbitrary size, we use a self-referential data definition. 52 00:03:43,610 --> 00:03:47,616 Neutrally referencial is something we'll talk about in another week. 53 00:03:47,616 --> 00:03:51,398 So if we follow this link, it says that we need to use, for our arbitrary size 54 00:03:51,398 --> 00:03:54,523 information. We need to use a well formed 55 00:03:54,523 --> 00:03:58,975 self-referential data definitioning/g. So that's how the how to design data 56 00:03:58,975 --> 00:04:02,840 recipe accounts for what we've seen in the code so far. 57 00:04:02,840 --> 00:04:07,366 Let's go back to the code now, and let's talk quickly about the examples for 58 00:04:07,366 --> 00:04:14,470 self-referential data definitions, it's good to have examples of the base case. 59 00:04:14,470 --> 00:04:19,040 If there's more than one base case, then have examples of both base cases. 60 00:04:19,040 --> 00:04:21,812 They tend to be kind of trivial, but I like to put them in anyways. 61 00:04:21,812 --> 00:04:26,030 And you should have examples of the self-referential case. 62 00:04:26,030 --> 00:04:29,038 In this particular data definition, I probably could have done with just two 63 00:04:29,038 --> 00:04:32,810 examples rather than three. So I probably could have done with 64 00:04:32,810 --> 00:04:36,257 example one and example three. It's fine to have an additional one. 65 00:04:36,257 --> 00:04:40,263 Now, let me scroll a little bit and talk about the template. 66 00:04:40,263 --> 00:04:46,230 As we saw before at the beginning of the templates relatively straightforward. 67 00:04:46,230 --> 00:04:49,080 It's one of, with two cases, so that got us the cond. 68 00:04:49,080 --> 00:04:54,162 The first case is atomic distinct empty, so that got us cond empty questionmark 69 00:04:54,162 --> 00:05:00,650 los and dot dot dot. This case, the second case, is cond, so 70 00:05:00,650 --> 00:05:05,461 that's compound. We take the cons apart into it's first 71 00:05:05,461 --> 00:05:10,012 and it's rest. But then the question is how do we get 72 00:05:10,012 --> 00:05:13,983 this fn-for-los? Well the reason we got that fn-for-los, 73 00:05:13,983 --> 00:05:19,818 let me just back up a little bit to where we were right at that point in time. 74 00:05:19,818 --> 00:05:25,450 We know that first los was going to be a string. 75 00:05:25,450 --> 00:05:29,662 And we knew that rest los was ListOfString so we're not going to do 76 00:05:29,662 --> 00:05:34,603 anything with first los because its primitive type string is a primitive 77 00:05:34,603 --> 00:05:38,950 type. But with rest los here's where we're 78 00:05:38,950 --> 00:05:44,030 getting the self reference this is self reference here back to listed string. 79 00:05:44,030 --> 00:05:48,830 Well we take the rest of los, we're holding a value of type listed string. 80 00:05:48,830 --> 00:05:56,003 And so there's a special template rule called the self reference rule. 81 00:05:56,003 --> 00:06:07,302 And we use it in this case. And the self reference rule says, wrap 82 00:06:07,302 --> 00:06:14,630 that selector in a call to the template function itself. 83 00:06:16,120 --> 00:06:18,268 In this thing is what's called natural recursion. 84 00:06:18,268 --> 00:06:23,858 It's a recursion that shows up, exactly where in the type comment we have a self 85 00:06:23,858 --> 00:06:28,360 reference. So, what we have so far, is arbitrary 86 00:06:28,360 --> 00:06:33,038 size data, well formed self-referential data definition. 87 00:06:33,038 --> 00:06:37,902 Have examples of, the base case and self-reference case and in the template, 88 00:06:37,902 --> 00:06:43,560 when you hit the self-reference, put in a natural recursion. 89 00:06:43,560 --> 00:06:47,520 That last bit shows up in the data driven templates page. 90 00:06:47,520 --> 00:06:51,414 Right here where it says, if you have a self reference, form a natural recursion 91 00:06:51,414 --> 00:06:56,670 with a call to this type's template function, and that's what we did here. 92 00:06:56,670 --> 00:06:59,725 We put a call to this type's template function, because we had a self reference 93 00:06:59,725 --> 00:07:04,278 there. And that's why this call, this natural 94 00:07:04,278 --> 00:07:10,860 recursion corresponds exactly to this self-reference. 95 00:07:10,860 --> 00:07:14,530 And I've tried to draw the arrows here to show that correspondence clearly. 96 00:07:14,530 --> 00:07:18,312 So from now on, whenever you see a self-reference in a type comment, you'll 97 00:07:18,312 --> 00:07:23,870 immediately know that there's going to be a natural recursion in the template. 98 00:07:23,870 --> 00:07:25,670 Now let's look at the function we designed. 99 00:07:25,670 --> 00:07:30,160 So the signature is pretty straightforward. 100 00:07:30,160 --> 00:07:33,263 Nothing really new here, except that it does consume ListOfString. 101 00:07:33,263 --> 00:07:37,423 The purpose, similarly, we knew how to do, and the stub, and the check-expects 102 00:07:37,423 --> 00:07:42,107 look pretty familiar. But there are a couple things I want to 103 00:07:42,107 --> 00:07:47,770 note here about check-expects for functions operating on lists. 104 00:07:47,770 --> 00:07:52,200 First, remember that check-expects are always examples first and tests later. 105 00:07:52,200 --> 00:07:55,380 So, we use them as examples to help us figure out what we're doing. 106 00:07:55,380 --> 00:07:59,199 And with that in mind, it's always a good idea to have the base case example first, 107 00:07:59,199 --> 00:08:03,330 the base case test first. That's what I have here. 108 00:08:03,330 --> 00:08:06,700 I have contains-ubc at empty as my first test. 109 00:08:06,700 --> 00:08:10,293 Partly, that helps us figure out the simplest case first. 110 00:08:10,293 --> 00:08:14,199 And also, many tests of these functions end up at the base case, and so if the 111 00:08:14,199 --> 00:08:19,390 base case result is wrong, that can affect other tests. 112 00:08:19,390 --> 00:08:22,090 So it's good to get the base case debugged first. 113 00:08:22,090 --> 00:08:25,190 So there's two reasons to put the base case first, one it helps us figure out 114 00:08:25,190 --> 00:08:30,240 the simplest thing first and the other it makes sure when we run the test. 115 00:08:30,240 --> 00:08:34,580 That the base case works properly before we cast the other cases. 116 00:08:34,580 --> 00:08:37,700 And another general guideline for functions operating on lists is to be 117 00:08:37,700 --> 00:08:40,924 sure that you have a test that operates on a list thats at least two elements 118 00:08:40,924 --> 00:08:44,650 long. That's because sometimes there's certain 119 00:08:44,650 --> 00:08:48,915 kinds of bugs you can introduce that don't show up in one element lists. 120 00:08:48,915 --> 00:08:52,506 This particular example is also an example of a function that has two 121 00:08:52,506 --> 00:08:56,576 difference cases in it. There's cases where it finds the string 122 00:08:56,576 --> 00:08:59,235 it's looking for and cases where it doesn't. 123 00:08:59,235 --> 00:09:03,090 And so, in that case, you have to be able to test the true and false case. 124 00:09:03,090 --> 00:09:07,140 Finally, let's look at the function itself and to look at the function. 125 00:09:07,140 --> 00:09:10,060 What I want to do is I'm going to back up. 126 00:09:10,060 --> 00:09:13,525 So what I'm going to do is I'm going to Delete this and go back to the point 127 00:09:13,525 --> 00:09:19,757 where we just had the template. When you Copy the template down, for a 128 00:09:19,757 --> 00:09:25,570 template based on our type with self reference. 129 00:09:25,570 --> 00:09:30,178 The new template has a natural recursion in it and its very important when you 130 00:09:30,178 --> 00:09:34,806 rename the function.. That you rename both the function 131 00:09:34,806 --> 00:09:40,750 definition and any natural recursions. That's very important, and we'll see why 132 00:09:40,750 --> 00:09:45,500 in a minute. So now, let me start coding the details. 133 00:09:45,500 --> 00:09:49,160 Let's see if the function is operating on a list that's empty. 134 00:09:49,160 --> 00:09:54,710 Then we can't find UBC in an empty list, so that would be false. 135 00:09:54,710 --> 00:09:57,770 Otherwise, these examples tell me that there's two different cases depending on 136 00:09:57,770 --> 00:10:02,676 the first item in the list. The first item is UBC, we produce true, 137 00:10:02,676 --> 00:10:07,514 if it's not, we produce false. So that makes me put an if in here, and I 138 00:10:07,514 --> 00:10:13,368 say string equal? UBC, if the first item in the list is 139 00:10:13,368 --> 00:10:22,140 UBC, we're going to produce true. In otherwise, what do we need to do? 140 00:10:22,140 --> 00:10:26,340 Well, first thing on the list, might not be the UBC but there might be, UBC 141 00:10:26,340 --> 00:10:32,230 further down the list. So, we need to go look further down on 142 00:10:32,230 --> 00:10:36,832 the list and the key point here is, that we want you to get you to trust the 143 00:10:36,832 --> 00:10:42,724 natural recursion. At this point in time, you need to know 144 00:10:42,724 --> 00:10:48,139 is UBC in the rest of the list. And because the template has included a 145 00:10:48,139 --> 00:10:52,477 natural recursion. And because that natural recursion came 146 00:10:52,477 --> 00:10:56,419 from a type with well formed self-reference, you can count on the 147 00:10:56,419 --> 00:11:01,050 natural recursion to work. So we're just going to trust that 148 00:11:01,050 --> 00:11:05,060 contains-ubc of rest los does what we need it to do. 149 00:11:05,060 --> 00:11:09,086 The key thing is I want you to avoid the temptation to edit in here. 150 00:11:09,086 --> 00:11:12,930 Trust the natural recursion, that's the game. 151 00:11:12,930 --> 00:11:16,765 And the reason you can trust it is because it came from a well formed self 152 00:11:16,765 --> 00:11:21,489 referencial type. Let's see, all four attempts pass. 153 00:11:21,489 --> 00:11:26,920 What I'd like you to do now, is go look at the How to Design Functions. 154 00:11:26,920 --> 00:11:31,190 And how to design data, and data driven templates webpages. 155 00:11:31,190 --> 00:11:36,140 And pay attention to the parts that talk specifically about designing with lists. 156 00:11:36,140 --> 00:11:40,227 Just go ahead and review that, and then you'll be in a good position to keep 157 00:11:40,227 --> 00:11:45,957 designing with lists going forward. And remember, the big summary of kind of 158 00:11:45,957 --> 00:11:50,511 what we've seen so far is, if you have arbitrary size information, then you need 159 00:11:50,511 --> 00:11:56,844 arbitrary size data. That requires a well-formed 160 00:11:56,844 --> 00:12:01,678 self-referential type comment. That leads to a natural recursion in the 161 00:12:01,678 --> 00:12:04,960 template. That leads to a recursive call in the 162 00:12:04,960 --> 00:12:09,892 function. You should test the base case first, and 163 00:12:09,892 --> 00:12:14,730 you should always trust the natural recursion.