1 00:00:06,070 --> 00:00:09,560 In the next few videos, we're going to learn how to design with lists. 2 00:00:09,560 --> 00:00:12,745 That's going to include changes to both the how to design functions, and how to 3 00:00:12,745 --> 00:00:18,168 design data recipe. Now, the way I'm going to present those 4 00:00:18,168 --> 00:00:23,380 changes is different than I used to originally cover those recipes. 5 00:00:23,380 --> 00:00:26,920 What I'm going to do, starting in this video, is charge into a data design 6 00:00:26,920 --> 00:00:31,550 problem with lists. And when I get to a place that, I don't 7 00:00:31,550 --> 00:00:34,699 know what to do. That the recipe doesn't already tell me 8 00:00:34,699 --> 00:00:37,720 what to do I'm going to make a lucky guess and it's all going to work out 9 00:00:37,720 --> 00:00:41,470 fantastically. I'll do that with the data recipe in this 10 00:00:41,470 --> 00:00:45,240 video, and I'll do it with the function recipe in the next video. 11 00:00:45,240 --> 00:00:49,146 And then in the third video, I'm going to go back and explain why those lucky 12 00:00:49,146 --> 00:00:55,970 guesses really were the right guesses and formally include them into the recipes. 13 00:00:55,970 --> 00:00:58,870 So that you'll be able to design with lists systematically from that point on. 14 00:00:58,870 --> 00:01:02,083 This problem has to do with designing a program that's going to keep track of 15 00:01:02,083 --> 00:01:05,772 your favorite Quidditch teams. So, we're going to design a data 16 00:01:05,772 --> 00:01:08,757 definition to represent a list of Quidditch teams. 17 00:01:08,757 --> 00:01:12,137 Remembering always that when we design data definitions, what we're doing is 18 00:01:12,137 --> 00:01:15,340 working out how to represent information as data. 19 00:01:16,360 --> 00:01:19,750 Let me just do a couple comment boxes here. 20 00:01:19,750 --> 00:01:24,480 And in this box, we'll put some examples of the information. 21 00:01:24,480 --> 00:01:32,224 So, I'm going to focus on some of the Canadian Quidditch teams, one of which is 22 00:01:32,224 --> 00:01:38,528 UBC. One of which is McGill, and one of which 23 00:01:38,528 --> 00:01:45,251 is the team Who Must Not Be Named. And by that, I don't mean Toronto, I mean 24 00:01:45,251 --> 00:01:49,010 a team that's actually chosen that name. Which I think was a little silly, but 25 00:01:49,010 --> 00:01:51,968 never mind. So, now let's think about the data that 26 00:01:51,968 --> 00:01:55,830 might be used to represent that. You know, those things look a lot like 27 00:01:55,830 --> 00:01:58,036 strings to me. Strings look like a good way to represent 28 00:01:58,036 --> 00:02:04,350 that. So, for example, you might represent the 29 00:02:04,350 --> 00:02:12,870 team UBC As the string UBC, and, and so on. 30 00:02:12,870 --> 00:02:16,060 So, that's how we might represent some individual teams. 31 00:02:16,060 --> 00:02:19,340 Now, how might we represent a list of teams, right? 32 00:02:19,340 --> 00:02:25,480 A list of my favorite teams. Well, we saw how to do that using conses. 33 00:02:25,480 --> 00:02:31,018 I would say cons. Let's suppose that my two favorite teams 34 00:02:31,018 --> 00:02:39,240 are, those that my favorite teams are UBC and McGill. 35 00:02:39,240 --> 00:02:44,050 That's kind of how we would represent that using lists. 36 00:02:44,050 --> 00:02:47,770 So, now I've thought some about the information and the data, and I'm ready 37 00:02:47,770 --> 00:02:51,802 to go ahead and write out the actual data definition. 38 00:02:51,802 --> 00:02:57,860 So let's see, what I've got here is kind of a list of string. 39 00:02:57,860 --> 00:03:01,572 Every, every element of this list is a string, so I'm going to go ahead and call 40 00:03:01,572 --> 00:03:06,122 the type, list of string. Now I could call it list of team, but I'm 41 00:03:06,122 --> 00:03:11,171 going to call it list of string. We'll see some examples where you'd list 42 00:03:11,171 --> 00:03:14,782 introduce another type name, for example team. 43 00:03:14,782 --> 00:03:18,233 We'll see some of those a little bit later this week. 44 00:03:18,233 --> 00:03:23,892 So, I'm going to say list of string is. Now here, there's an interesting little 45 00:03:23,892 --> 00:03:28,666 thing, which is here's one list of favorite teams, and the rest of that list 46 00:03:28,666 --> 00:03:34,841 is a list of favorite teams. And the rest of that list is also a list 47 00:03:34,841 --> 00:03:39,640 of favorite teams, but it's an empty list. 48 00:03:39,640 --> 00:03:43,609 So, buried in the midst of here is this subtle point that empty would also be a 49 00:03:43,609 --> 00:03:47,601 good example. Let's just suppose you didn't like any of 50 00:03:47,601 --> 00:03:52,906 the current Quidditch teams, your list of favorite teams, not with a quote there. 51 00:03:52,906 --> 00:03:57,167 Empty like that would also be an example. So, the way I'm going to write this type 52 00:03:57,167 --> 00:04:00,150 comment, and again, we'll come back to this. 53 00:04:00,150 --> 00:04:02,330 Remember, I said I was going to kind of get lucky. 54 00:04:02,330 --> 00:04:06,870 A few times in this design and then after the data design and the function design. 55 00:04:06,870 --> 00:04:11,670 I'll explain it all. The way I'm going to write this type 56 00:04:11,670 --> 00:04:17,826 comment is like this. I'm going to say that a list of string is 57 00:04:17,826 --> 00:04:24,340 one of either empty or cons string, list of string. 58 00:04:24,340 --> 00:04:28,630 Now, there's an interesting thing going on there, which is in the middle of this 59 00:04:28,630 --> 00:04:32,591 type comment. I refer to the type comment itself, so I 60 00:04:32,591 --> 00:04:37,955 define a list of string and in the middle I refer to the list of string. 61 00:04:37,955 --> 00:04:40,270 And we're going to talk a great deal more about that. 62 00:04:40,270 --> 00:04:42,480 I'm just pointing out that that is there when you see that, that's what I mean to 63 00:04:42,480 --> 00:04:47,068 say. Let's do an interpretation. 64 00:04:47,068 --> 00:04:53,738 Interpretation, a list of strings, because each element in these cons is a 65 00:04:53,738 --> 00:04:58,990 string. And now let's do some examples. 66 00:04:58,990 --> 00:05:13,870 Well, one example is empty, and another example is say, just McGill and empty. 67 00:05:13,870 --> 00:05:16,760 And another example, oops, that's not one, that, that's two. 68 00:05:16,760 --> 00:05:21,648 And another example is cons. UBC, cons, McGill, and empty. 69 00:05:21,648 --> 00:05:28,893 Before we go on, let's see if the type comment we have matches the examples we 70 00:05:28,893 --> 00:05:33,906 have. We're going to talk more about the type 71 00:05:33,906 --> 00:05:38,017 comment in upcoming video, as I said. But, it's a pretty good question right 72 00:05:38,017 --> 00:05:41,303 now to at least make sure that the type comment admits the three examples we 73 00:05:41,303 --> 00:05:45,100 have. So, let's try that. 74 00:05:45,100 --> 00:05:48,490 The value of LOS1 is empty. So the question we have to ask is, is 75 00:05:48,490 --> 00:05:53,570 empty ListOfString? Does empty match the type ListOfString? 76 00:05:53,570 --> 00:05:56,655 Well let's see, the type definition for ListOfString is this. 77 00:05:56,655 --> 00:06:00,730 And there's two cases, so let's see, does empty match the first case? 78 00:06:00,730 --> 00:06:04,208 Yes, it does. So, now we know that empty is list of 79 00:06:04,208 --> 00:06:06,720 string. That wasn't that hard. 80 00:06:06,720 --> 00:06:11,520 Now let's ask about LOS2, which is cons McGill empty. 81 00:06:12,710 --> 00:06:15,202 Again, we want to ask is that list of string? 82 00:06:15,202 --> 00:06:19,880 Well, here's the type definition for list of string. 83 00:06:19,880 --> 00:06:23,070 And there's two cases. Let's see, does cons McGill empty match 84 00:06:23,070 --> 00:06:25,670 the first case? No, it doesn't. 85 00:06:25,670 --> 00:06:31,030 Cons McGill empty definitely isn't empty. Let's try the second case. 86 00:06:31,030 --> 00:06:34,330 Well, cons McGill empty starts out with open parin cons, which is how the second 87 00:06:34,330 --> 00:06:39,384 case starts out, so that looks promising. And cons McGill empty has this closed 88 00:06:39,384 --> 00:06:43,780 parin at the end, which the second case also has. 89 00:06:43,780 --> 00:06:47,280 So that looks promising. Now the question we have to ask is, is 90 00:06:47,280 --> 00:06:53,030 McGill, is the second thing in cons McGill empty, McGill, is that string? 91 00:06:53,030 --> 00:06:56,236 Well, yes, McGill is string, that's trivially true. 92 00:06:56,236 --> 00:07:01,180 We know that McGill is the string. So because that's yes, we get a little 93 00:07:01,180 --> 00:07:06,350 bit more of a match between cons McGill and the second case of list of string. 94 00:07:06,350 --> 00:07:10,090 Now we need to ask the question, is empty list of string? 95 00:07:10,090 --> 00:07:13,800 Well we've done this before, but I'm going to do it again just for 96 00:07:13,800 --> 00:07:18,334 completeness. So we ask the question, is empty 97 00:07:18,334 --> 00:07:21,828 ListOfString? We look at the type definition for 98 00:07:21,828 --> 00:07:25,176 ListOfString. And its listed string is one of there's 99 00:07:25,176 --> 00:07:28,605 two cases. And empty matches the first case. 100 00:07:28,605 --> 00:07:34,686 So yes, empty is ListOfString. So going back into the prior matching, 101 00:07:34,686 --> 00:07:38,765 that means empty matches list of string there and there. 102 00:07:38,765 --> 00:07:44,540 So, now we have a complete match. And we know that cons McGill empty is 103 00:07:44,540 --> 00:07:47,387 ListofString. And I think you can see that this would 104 00:07:47,387 --> 00:07:50,100 work for longer lists. It would just get boring if I had a list 105 00:07:50,100 --> 00:07:53,350 that had two elements in it, then I would end up having to go to list of string the 106 00:07:53,350 --> 00:07:57,035 first time. List of string the second time, and list 107 00:07:57,035 --> 00:08:00,110 of string the third time to get the empty at the end. 108 00:08:00,110 --> 00:08:04,301 It would just keep going. In some sense, what's happening here is 109 00:08:04,301 --> 00:08:08,006 that this self reference in the type comment replacing the type comment with a 110 00:08:08,006 --> 00:08:14,170 list of string refers to itself is letting us match arbitrarily long lists. 111 00:08:14,170 --> 00:08:18,070 Because we just start the matching over with the last of the list, as many times 112 00:08:18,070 --> 00:08:22,330 as we need to, before we finally get to the empty case. 113 00:08:22,330 --> 00:08:26,370 We'll talk more about this the video after this next one. 114 00:08:28,130 --> 00:08:32,304 Now, let's do the template. I'm going to say define fun for, and I'm 115 00:08:32,304 --> 00:08:39,780 not going to write list of string here. For these list of types, we're going to 116 00:08:39,780 --> 00:08:45,104 let you abbreviate it like this. And let's see. 117 00:08:45,104 --> 00:08:49,730 Template rules used. Now, the template starts off easily 118 00:08:49,730 --> 00:08:52,325 enough. First word after is is one of, so the 119 00:08:52,325 --> 00:09:00,640 first rule is the one of rule. And there's two choices. 120 00:09:00,640 --> 00:09:04,780 So that means I'm going to put in a cond with one question, one answer, and 121 00:09:04,780 --> 00:09:11,311 another question and another answer. And that's the beginning of the template. 122 00:09:12,800 --> 00:09:17,550 Now let's see, the next part is easy after the one of isn't empty. 123 00:09:19,300 --> 00:09:24,680 So, that's an atomic distinct empty because empty is a single value. 124 00:09:24,680 --> 00:09:29,630 There's a single empty list. So, atomic distinct empty. 125 00:09:29,630 --> 00:09:34,052 The predicate for empty is empty question mark, and it's an atomic distinct so we 126 00:09:34,052 --> 00:09:41,130 just have dot dot dot in the answer. That's atomic distinct empty. 127 00:09:41,130 --> 00:09:45,311 Now, we have this case. And remember what I said. 128 00:09:45,311 --> 00:09:51,526 The way we're going to think about a cons is of a cons as compound data. 129 00:09:51,526 --> 00:09:55,160 So, we're going to use the compound rule here. 130 00:09:55,160 --> 00:10:00,440 And if we go look at the data driven templates page, we'll see that cons is 131 00:10:00,440 --> 00:10:05,560 one of the examples it gives for compound. 132 00:10:05,560 --> 00:10:10,510 So it's compound, cons, string, list of string. 133 00:10:10,510 --> 00:10:19,370 It's the last question of an itemization, so we can make the question be else. 134 00:10:19,370 --> 00:10:21,857 And then it's dot, dot, dot and the two selectors. 135 00:10:21,857 --> 00:10:28,364 Well, the selectors are first of los, and rest of lost. 136 00:10:28,364 --> 00:10:35,928 And the type of first is string, because it's the column of strings and the list 137 00:10:35,928 --> 00:10:40,985 of strings. So, the type of first is string. 138 00:10:40,985 --> 00:10:45,692 And the type of the rast is list of string. 139 00:10:45,692 --> 00:10:50,939 Now here, what I'm going to do, and I'm going to talk more about this. 140 00:10:50,939 --> 00:10:55,749 Not in this video or the next video, but in the video after I'm going to come back 141 00:10:55,749 --> 00:10:59,218 to this point. So now, I'm going to kind of just do 142 00:10:59,218 --> 00:11:01,320 something. This is what I mean by getting lucky. 143 00:11:01,320 --> 00:11:04,210 I'm going to do something lucky. I won't explain why. 144 00:11:04,210 --> 00:11:10,352 We'll explain why in two videos. But I'm going to put, this in the 145 00:11:10,352 --> 00:11:17,860 template right here. I'm going to run that template. 146 00:11:17,860 --> 00:11:21,392 There are no errors, so it's well formed. We'll comment it out. 147 00:11:21,392 --> 00:11:27,837 And now, at this point, I can delete this scratch work up here. 148 00:11:27,837 --> 00:11:32,940 And there's a data definition for representing Quidditch teams or lists of 149 00:11:32,940 --> 00:11:38,974 Quidditch teams using lists of string. In the next video, we're going to design 150 00:11:38,974 --> 00:11:41,580 a function operating on these lists.