1 00:00:06,070 --> 00:00:09,038 In this video, I'm going to step back from the details of the functions 2 00:00:09,038 --> 00:00:12,324 operating on lists that we've been designing, and give you a more abstract 3 00:00:12,324 --> 00:00:18,790 way of looking at those functions. Now, what do I mean when I say abstract? 4 00:00:19,820 --> 00:00:23,200 Well, I mean a view of those functions that's less detailed but still captures 5 00:00:23,200 --> 00:00:26,632 their essential structure, and still tells us something important about what 6 00:00:26,632 --> 00:00:30,802 they do. In this video, I'm not making any changes 7 00:00:30,802 --> 00:00:35,436 or additions to the design recipes. You're still going to design functions 8 00:00:35,436 --> 00:00:40,380 that operate on lists the same way. What this video does do is gives you a 9 00:00:40,380 --> 00:00:44,467 new perspective on why those functions work, and how their template sets them up 10 00:00:44,467 --> 00:00:49,024 to work. And so, what I want you to do is take 11 00:00:49,024 --> 00:00:52,000 this material now, and maybe watch it again once or twice in the next couple 12 00:00:52,000 --> 00:00:55,984 weeks. And I think it'll really help you 13 00:00:55,984 --> 00:01:00,520 designing functions that operate on all kinds of arbitrary sized data. 14 00:01:00,520 --> 00:01:04,580 To understand how those functions work, and what their templates do for them. 15 00:01:06,290 --> 00:01:09,140 So far, this week we've seen two list of types. 16 00:01:09,140 --> 00:01:12,717 List of string and list of number. Both of them have well formed self 17 00:01:12,717 --> 00:01:15,794 reference. Because of the self reference in the type 18 00:01:15,794 --> 00:01:18,986 commands, both of them also have a natural recursion in the template 19 00:01:18,986 --> 00:01:23,606 functions. In fact, these two types are very similar 20 00:01:23,606 --> 00:01:28,682 to each other. They really only differ in the name of 21 00:01:28,682 --> 00:01:34,315 the type of value included. Strings in one case, number in the other 22 00:01:34,315 --> 00:01:37,682 case. So, for what I want to talk about now, we 23 00:01:37,682 --> 00:01:42,380 can just look at one of them. We'll just look at list of number. 24 00:01:42,380 --> 00:01:46,460 Again, we see that it has a self reference in the type comment which leads 25 00:01:46,460 --> 00:01:51,893 to a natural recursion in the template. What I want to do now is look for a 26 00:01:51,893 --> 00:01:56,051 minute at how all of the three functions we've designed so far, each fill the 27 00:01:56,051 --> 00:02:02,520 different holes in the template. Here's what I mean by that. 28 00:02:02,520 --> 00:02:07,095 If we look at Sum on the left, and the form for list of number template on the 29 00:02:07,095 --> 00:02:14,110 right, then we look at what I call for now the red hole in the template. 30 00:02:14,110 --> 00:02:15,680 I'm going to give it a better name in a minute. 31 00:02:15,680 --> 00:02:19,290 But for now, we'll just call it the red space in the template. 32 00:02:19,290 --> 00:02:23,133 In the sum function: the red space gets filled with 0, the green space gets 33 00:02:23,133 --> 00:02:27,320 filled with plus. Nothing changes in the blue space. 34 00:02:27,320 --> 00:02:33,770 We just leave it the way it was. Count starts offquite similar to sum. 35 00:02:33,770 --> 00:02:37,674 It fills the red space with zero, the green space with plus, but it changes 36 00:02:37,674 --> 00:02:43,191 what happens in the blue space. Whereas in sum, we add the first of lon 37 00:02:43,191 --> 00:02:50,430 into the natural recursion, in count, we just add 1 into the natural recursion. 38 00:02:50,430 --> 00:02:56,830 Now, let's look at contains ubc. In contains-ubc, the red space is false. 39 00:02:56,830 --> 00:03:00,190 And look what I've done here with the blue and the green. 40 00:03:00,190 --> 00:03:04,545 For the blue, I've said that what happens in this function is that it wraps string 41 00:03:04,545 --> 00:03:10,790 equals question mark to ubc around first and los, and I'm calling that the blue. 42 00:03:10,790 --> 00:03:15,078 And I've got green stuff both before and after the blue, it's that if expression, 43 00:03:15,078 --> 00:03:18,820 with its true answer and its false answer. 44 00:03:18,820 --> 00:03:21,965 Why am I doing that? Well, here's why. 45 00:03:21,965 --> 00:03:25,869 Let me now talk about the name that I want to give to each of these three spots 46 00:03:25,869 --> 00:03:29,673 in the template. I'm going to call the red spot base, 47 00:03:29,673 --> 00:03:33,390 because really what's sitting in the red spot is the base case result of this 48 00:03:33,390 --> 00:03:36,856 function. What the function produces in the base 49 00:03:36,856 --> 00:03:41,520 case. For sum, the base case result is zero. 50 00:03:41,520 --> 00:03:45,925 For count, the base case result is zero. And for contains-ubc the base case result 51 00:03:45,925 --> 00:03:49,090 is false. That's fairly straightforward. 52 00:03:49,090 --> 00:03:52,440 The blue I'm going to call the contribution of the first, or the 53 00:03:52,440 --> 00:03:56,519 contribution of the first to the overall result. 54 00:03:56,519 --> 00:04:00,708 So, in the case of sum, each first element of the list, or each element of 55 00:04:00,708 --> 00:04:07,771 the list when it's its turn to be first, contributes itself to the overall result. 56 00:04:07,771 --> 00:04:11,677 Because sum is sitting there adding together all the numbers in the list. 57 00:04:11,677 --> 00:04:17,499 Now, how does that contribution work? Well, that's what combination means. 58 00:04:17,499 --> 00:04:22,278 Combination refers to the way in which the final function combines the 59 00:04:22,278 --> 00:04:28,692 contribution of the first with the result of the natural recursion. 60 00:04:30,360 --> 00:04:34,975 So, in the case of sum, the combination is to add the contribution of the first, 61 00:04:34,975 --> 00:04:40,240 which is itself, to the result of the natural recursion. 62 00:04:40,240 --> 00:04:43,986 Let's look at count for a second. We already saw that the base case result 63 00:04:43,986 --> 00:04:46,960 of count is 0. What's the contribution of first in the 64 00:04:46,960 --> 00:04:48,870 case of count? Well, it's 1. 65 00:04:48,870 --> 00:04:53,292 When we count the number of elements in the list, we don't care what each element 66 00:04:53,292 --> 00:04:58,777 is, we just care that it exists. So, each element contributes one to the 67 00:04:58,777 --> 00:05:02,700 overall result, and the combination is still a plus. 68 00:05:02,700 --> 00:05:06,462 Now that we understand better what the blue and the green are, the contribution 69 00:05:06,462 --> 00:05:10,281 of the first, and the way in which that contribution is combined with the natural 70 00:05:10,281 --> 00:05:15,421 recursion. Now, you can see why I colored things the 71 00:05:15,421 --> 00:05:20,101 way I did in contains ubc. The contribution of the first is just to 72 00:05:20,101 --> 00:05:23,641 say is this element, is the first element of the list equal to ubc? 73 00:05:23,641 --> 00:05:31,129 And the combination is to say, well, if the contribution of the first is true, 74 00:05:31,129 --> 00:05:37,448 then produce true. If the contribution of the first is 75 00:05:37,448 --> 00:05:41,530 false, then produce the natural recursion. 76 00:05:41,530 --> 00:05:45,137 Now, why am I talking about this now. After all, you've just designed three 77 00:05:45,137 --> 00:05:48,435 list functions, this may seem a bit too hard for right now. 78 00:05:48,435 --> 00:05:51,815 The reason I'm doing this now is to give you a bit of a preview of something we're 79 00:05:51,815 --> 00:05:56,154 going to do in a couple weeks. In a couple weeks, you're going to see 80 00:05:56,154 --> 00:06:00,230 that because we've been working really systematically. 81 00:06:00,230 --> 00:06:04,718 With well formed typed comments, which produced templates in a well defined way, 82 00:06:04,718 --> 00:06:08,876 so that a lot of our functions that operate on lists and other arbitrary size 83 00:06:08,876 --> 00:06:14,456 data have a common form. It's going to be possible for us to write 84 00:06:14,456 --> 00:06:18,548 functions like sum, and count, and contains-ubc really in just one line of 85 00:06:18,548 --> 00:06:22,920 code. You'll write them by basically talking 86 00:06:22,920 --> 00:06:25,883 about how to fill the spaces in this table. 87 00:06:25,883 --> 00:06:30,520 And we're not ready to do that now. And I'm not trying to say that you need 88 00:06:30,520 --> 00:06:33,133 to do that now. You don't need to be able to design one 89 00:06:33,133 --> 00:06:36,170 of these functions just by filling in the table. 90 00:06:36,170 --> 00:06:40,257 The reason I'm showing you this now is so that when you design these functions the 91 00:06:40,257 --> 00:06:44,222 way we've talked about this week, you follow the whole recipe and you write out 92 00:06:44,222 --> 00:06:50,430 the template in detail, and then you fill it in based on the examples. 93 00:06:51,450 --> 00:06:55,290 Maybe when you're done designing the functions, think for a minute about how 94 00:06:55,290 --> 00:06:58,850 that function's row in this table would look. 95 00:06:58,850 --> 00:07:02,882 And I think that'll help you as we go on, form a more general view of what these 96 00:07:02,882 --> 00:07:07,350 functions are. So that in a couple when we get to what's 97 00:07:07,350 --> 00:07:10,925 called function abstraction, you'll really be ready to see how it simplifies 98 00:07:10,925 --> 00:07:13,930 the writing of these functions.