1 00:00:06,020 --> 00:00:08,965 So now, we're going to design a function that operates on list of string. 2 00:00:08,965 --> 00:00:12,030 And remember what I said on the last video. 3 00:00:12,030 --> 00:00:15,410 We still don't have all the changes we need to the how to design function recipe 4 00:00:15,410 --> 00:00:18,906 to do this. So, there's going to be a place in there 5 00:00:18,906 --> 00:00:23,303 where I'm going to make a lucky guess. And that lucky guess is going to turn out 6 00:00:23,303 --> 00:00:26,572 splendidly for me. And then in the next video, I'm going to 7 00:00:26,572 --> 00:00:30,862 come back and really explain away all those lucky guesses, so that you can make 8 00:00:30,862 --> 00:00:34,398 them, too. We're starting where we left off in the 9 00:00:34,398 --> 00:00:37,475 last video. We have a data definition for list and 10 00:00:37,475 --> 00:00:41,594 string. And that's the type that we're using to 11 00:00:41,594 --> 00:00:46,246 represent lists of quidditch teams. Remember, there were three things about 12 00:00:46,246 --> 00:00:49,150 this data definition that I said I would talk more about later, and that'll be in 13 00:00:49,150 --> 00:00:53,364 the next video. One was this self reference here at the 14 00:00:53,364 --> 00:00:59,620 top, well, is the fact that I put in this funny call to fun for los here. 15 00:00:59,620 --> 00:01:03,640 And last thing is I didn't say what template rule caused me to put that fun 16 00:01:03,640 --> 00:01:07,531 for los. Now if we go down a little farther in 17 00:01:07,531 --> 00:01:11,613 this starter file, there's a second problem. 18 00:01:11,613 --> 00:01:14,928 And the problem here is we want to know whether your list of favorite Quidditch 19 00:01:14,928 --> 00:01:20,036 teams includes UBC. So, we're going to design a function that 20 00:01:20,036 --> 00:01:24,889 consumes list of string and produces true if the list includes UBC. 21 00:01:24,889 --> 00:01:26,990 So, this a how to design function problem. 22 00:01:26,990 --> 00:01:30,319 So, let's just get going. Signature first, it's going to consume a 23 00:01:30,319 --> 00:01:34,240 list of favorite quidditch teams. So, that's list of string. 24 00:01:34,240 --> 00:01:39,070 That's how we're representing that. And it's going to produce true if the 25 00:01:39,070 --> 00:01:43,322 list includes UBC. So, that means it's going to produce a 26 00:01:43,322 --> 00:01:45,420 Boolean. And let's see. 27 00:01:45,420 --> 00:01:54,168 We'll say produce true if los. We'll call it, includes UBC, and stub is 28 00:01:54,168 --> 00:01:59,325 defined. Let's say we'll call this function 29 00:01:59,325 --> 00:02:04,700 contains UBC, los. And we'll make the stub produce false. 30 00:02:04,700 --> 00:02:08,420 We'll say that that's the stub. Now, let's see some examples. 31 00:02:08,420 --> 00:02:12,380 We get some inspiration from the data examples that we have in the list of 32 00:02:12,380 --> 00:02:16,632 string data definition. So, empty is definitely a list of 33 00:02:16,632 --> 00:02:23,270 strings, let's try that. Let's say contains UBC of empty. 34 00:02:23,270 --> 00:02:29,249 Check expect of that. Well let's see, does the empty list 35 00:02:29,249 --> 00:02:32,120 contain ubc, well no it doesn't, so that's easy. 36 00:02:32,120 --> 00:02:38,962 That's False. Here's another one. 37 00:02:38,962 --> 00:02:50,758 Check expect contains ubc of cons McGill empty. 38 00:02:50,758 --> 00:02:54,959 Well, now UBC's not in there either. Let's make one that UBC is in. 39 00:02:54,959 --> 00:03:05,531 check-expect contains-ubc? cons UBC empty. 40 00:03:05,531 --> 00:03:12,119 That's true. Let's make one that UBC is in, but not in 41 00:03:12,119 --> 00:03:18,034 first position. Let's see, you can see who's in that 42 00:03:18,034 --> 00:03:24,630 list, so that'll be true. So ,we'll run that and make sure those 43 00:03:24,630 --> 00:03:31,143 examples are well formed, adn they are. Two are failing. 44 00:03:31,143 --> 00:03:44,180 Now let's see, let's go get the template. And we'll comment off the stub. 45 00:03:44,180 --> 00:03:51,781 We'll rename the template. Now it's time to code the body. 46 00:03:53,320 --> 00:03:55,480 So, let's see. Contains UBC. 47 00:03:55,480 --> 00:04:00,920 If los is empty, that's this first case, then intuition the purpose and this first 48 00:04:00,920 --> 00:04:07,300 example all three tell me that the result in that case is false. 49 00:04:07,300 --> 00:04:12,380 Now, what about this second case? So this is the case where, let's see, 50 00:04:12,380 --> 00:04:15,824 it's compound. This is the case where we have an actual 51 00:04:15,824 --> 00:04:18,902 cons. And this first of the cons will be a 52 00:04:18,902 --> 00:04:22,675 string. So that's a case like this, where we have 53 00:04:22,675 --> 00:04:28,814 McGill as the first element of the list. Or it's a case like this where we have 54 00:04:28,814 --> 00:04:35,174 ubc as the first element on the list. So, in that case, we would produce false 55 00:04:35,174 --> 00:04:39,667 and in that case it would produce true. So, lets' see it seems like or it could 56 00:04:39,667 --> 00:04:47,133 be this McGill is in the beginning of the list, but we need to keep looking. 57 00:04:47,133 --> 00:04:54,993 So, it seems like we need an f. And there's the f, and it seems like what 58 00:04:54,993 --> 00:04:59,840 we want to know is, the first thing in the list UBC. 59 00:04:59,840 --> 00:05:06,030 So, if the first thing in the list is UBC. 60 00:05:06,030 --> 00:05:10,520 That's this case here where the first thing in list is UBC. 61 00:05:10,520 --> 00:05:15,975 If the first thing in the list is UBC, then in that case we should choose true. 62 00:05:15,975 --> 00:05:23,160 You know, what do we need to do here, what do we need to do in this case? 63 00:05:23,160 --> 00:05:27,103 This is the case where the first thing in the list is not UBC. 64 00:05:28,840 --> 00:05:32,744 So that's a case like this one, where the first thing on the list is not UBC, and 65 00:05:32,744 --> 00:05:38,610 it's also a case like this one, where the first thing on the list is not UBC. 66 00:05:38,610 --> 00:05:42,273 In this case, UBC isn't anywhere on the list. 67 00:05:42,273 --> 00:05:46,263 But in this case, UBC is in the rest of the list. 68 00:05:46,263 --> 00:05:52,747 So, it seems like what we need to do here is, we got the rest of the list. 69 00:05:52,747 --> 00:05:58,141 It seems like we need to go look in the rest of the list to see whether the rest 70 00:05:58,141 --> 00:06:03,916 of the list contains UBC. That way in this case, when we go look in 71 00:06:03,916 --> 00:06:08,349 empty, there won't be UBC there. So, we'll produce false, and in this case 72 00:06:08,349 --> 00:06:12,995 when we go look in cons UBC empty, we'll find the UBC and produce true. 73 00:06:12,995 --> 00:06:17,875 So what we need right here, what we need fn for los to be, is we need fn for los 74 00:06:17,875 --> 00:06:23,325 to be a function. And if we give it a list of strings, it 75 00:06:23,325 --> 00:06:31,490 will tell us whether UBC is in that last. It would be nice to have such a function. 76 00:06:34,780 --> 00:06:38,730 Well, we do. Or I should say, we almost do. 77 00:06:38,730 --> 00:06:42,870 It says right here that there's a function that consumes list of strings 78 00:06:42,870 --> 00:06:48,560 and produces a Boolean and it produces true if the list includes UBC. 79 00:06:48,560 --> 00:06:53,820 And all of this says that the name of that function contains UBC. 80 00:06:53,820 --> 00:06:56,640 So, since there is a function that does that it says right there, there is. 81 00:06:56,640 --> 00:07:06,330 I can just make this the contains UBC, and now I'm done writing that function. 82 00:07:06,330 --> 00:07:09,432 Let's run it. All four test passed, and you may find 83 00:07:09,432 --> 00:07:13,158 that surprising. A funny thing happened here which is we 84 00:07:13,158 --> 00:07:18,181 wrote a function that used itself. This idea, which is called recursion, is 85 00:07:18,181 --> 00:07:23,381 deeply connected to the idea we saw in the last video which was self referenced 86 00:07:23,381 --> 00:07:28,590 in the type comment. For now, I'm just going to leave this 87 00:07:28,590 --> 00:07:32,414 video as it is, say that we're done doing this function. 88 00:07:32,414 --> 00:07:36,460 And then in the next video, I'll talk about why this all worked out.