1 00:00:00,025 --> 00:00:05,965 Now, it turns out you can represent arbitrary size information using compound 2 00:00:05,965 --> 00:00:12,810 date and that's something we'll do a little bit later this week. 3 00:00:14,030 --> 00:00:17,865 But the simplest form of arbitrary size data, is lists of values, and so, we're 4 00:00:17,865 --> 00:00:24,026 going to do lists of values first. Now, before I can talk about designing 5 00:00:24,026 --> 00:00:27,743 with lists, I have to show you the basic mechanisms that BSL gives us for 6 00:00:27,743 --> 00:00:31,860 representing lists. So this is kind of like what happened 7 00:00:31,860 --> 00:00:34,774 last week where first I showed you the define struct mechanism, and then we 8 00:00:34,774 --> 00:00:39,321 learned how to design compound data. First I'm going to talk about the BSL 9 00:00:39,321 --> 00:00:44,010 primitives for lists, and we'll do that in this video. 10 00:00:44,010 --> 00:00:47,460 And then over the next several videos we'll look at designing with lists. 11 00:00:48,810 --> 00:00:54,020 The primitive data that BSL gives us is called lists. 12 00:00:54,020 --> 00:00:58,160 Here's the value that BSL gives us for representing empty lists. 13 00:00:58,160 --> 00:01:02,100 So, that value empty is an empty list of anything you want. 14 00:01:02,100 --> 00:01:04,790 It's an empty list of strings. It's an empty list of hockey teams. 15 00:01:04,790 --> 00:01:08,142 It's an empty list of numbers. Since it's empty, it can be an empty list 16 00:01:08,142 --> 00:01:11,746 of anything. Now let's look at how to make a list that 17 00:01:11,746 --> 00:01:15,924 isn't empty. The way we do that is, we have a 18 00:01:15,924 --> 00:01:21,086 primitive cons. And if I do this, that is a list that's 19 00:01:21,086 --> 00:01:26,848 constructed by putting flames onto the front of this list here, which happens to 20 00:01:26,848 --> 00:01:33,793 be empty, so this is going to be a list of one element. 21 00:01:33,793 --> 00:01:46,100 Here is a list of two elements. And again, the way you read this is it 22 00:01:46,100 --> 00:01:49,796 says well construct a list in which Leafs is the first element and then add Leafs 23 00:01:49,796 --> 00:01:53,436 to the front of constructor list in which you add Flames to the front of the list 24 00:01:53,436 --> 00:01:59,007 empty. So that's a list of two elements. 25 00:02:04,950 --> 00:02:11,940 If we run this, Racket shows us the list, using this Cons notation it's called. 26 00:02:11,940 --> 00:02:14,910 So it shows us values that look very much like these expressions. 27 00:02:14,910 --> 00:02:16,310 But there's an important point to make here. 28 00:02:16,310 --> 00:02:20,279 Let me show you a third one of these. kind of a silly one, except to make this 29 00:02:20,279 --> 00:02:28,626 point. If I evaluate this third expression, the 30 00:02:28,626 --> 00:02:35,047 value that I get is cons, canucks, empty. What happens is when rachet evaluates 31 00:02:35,047 --> 00:02:40,503 this the string append, C, anucks produces the string Canucks and then the 32 00:02:40,503 --> 00:02:46,223 result in value, the resulting list Is the list formed with the string Canucks 33 00:02:46,223 --> 00:02:53,020 at the beginning of the list that's empty. 34 00:02:53,020 --> 00:02:59,130 So, you could put expressions as the operands for cons in expressions when BSL 35 00:02:59,130 --> 00:03:05,680 shows us values. It'll always be formed out of values. 36 00:03:05,680 --> 00:03:08,290 Now, lists can have more than just strings in them. 37 00:03:08,290 --> 00:03:12,360 For example, you could represent problem set quiz grades. 38 00:03:12,360 --> 00:03:15,570 And let's suppose we're doing very well in our problem set quizzes. 39 00:03:15,570 --> 00:03:21,610 So we've got a 10, a 9, and a 10. There's a list of three elements. 40 00:03:21,610 --> 00:03:23,557 The numbers, ten, nine and ten. And we can also make lists of images for 41 00:03:23,557 --> 00:03:28,394 example. So we have a list that's a square of size 42 00:03:28,394 --> 00:03:36,836 ten and solid and blue and let's see, the second element of the list would be a 43 00:03:36,836 --> 00:03:47,930 Triangle of size 20 that's solid and green, then empty. 44 00:03:47,930 --> 00:03:53,755 So lists can have all kinds of different values in them. 45 00:03:53,755 --> 00:03:57,826 Technically you can use the list mechanism to make Lists that have more 46 00:03:57,826 --> 00:04:02,497 than one type of data in them. The mechanism will do that, but our data 47 00:04:02,497 --> 00:04:05,840 definitions don't let us talk about that very well. 48 00:04:05,840 --> 00:04:09,340 So, we're not going to see values like that in this course. 49 00:04:09,340 --> 00:04:13,179 We clean this up a bit. And what I'm going to do is give some of 50 00:04:13,179 --> 00:04:17,160 these values names. Let me call this one, l one. 51 00:04:17,160 --> 00:04:30,940 And I'll call this one, l two. And I'll just get rid of this one, and 52 00:04:30,940 --> 00:04:40,770 I'll call this one l three. Now they've all got names. 53 00:04:40,770 --> 00:04:45,820 Now that we've made lists of things, we'd kind of like to know what's in the lists. 54 00:04:45,820 --> 00:04:49,141 So racket gives us two more primitives for doing that. 55 00:04:49,141 --> 00:04:53,331 One is called first. So first given a list, produces the first 56 00:04:53,331 --> 00:04:57,770 element of the list. So first of L1 produces flames. 57 00:04:57,770 --> 00:05:07,850 First of L2 would produce Ten, and first of L3 would produce that square. 58 00:05:07,850 --> 00:05:12,960 Okay, so that's first. First produces the first item in the 59 00:05:12,960 --> 00:05:18,735 list. First is kind of like a selector. 60 00:05:18,735 --> 00:05:22,920 That's because lists are kind of like compound data. 61 00:05:22,920 --> 00:05:25,632 Right? Cons is basically a compound data 62 00:05:25,632 --> 00:05:30,767 constructor saying, make a new list in which the first element is this, and the 63 00:05:30,767 --> 00:05:36,330 last of the list is the second operand For cons. 64 00:05:36,330 --> 00:05:40,200 So first is a selector that produces the first item in the list. 65 00:05:40,200 --> 00:05:43,080 And the name of the selector that produces the rest of the elements of the 66 00:05:43,080 --> 00:05:49,940 list is called rest. So rest of L1 is going to be empty. 67 00:05:49,940 --> 00:05:54,390 Because rest, everything in the list after flames is empty. 68 00:05:55,850 --> 00:06:07,520 We'll just quickly type these other two. Rest of L2 is cons9, cons10 empty. 69 00:06:07,520 --> 00:06:12,690 And rest of L3 is cons the triangle empty. 70 00:06:12,690 --> 00:06:16,699 So that's first and rest. Those are the bsl primitives for taking 71 00:06:16,699 --> 00:06:23,134 lists apart. Now let me ask you a question. 72 00:06:23,134 --> 00:06:30,935 Suppose what I want. How do I get the second element of L2. 73 00:06:30,935 --> 00:06:37,460 Now, bsl has a primitive called second. And, and has one called third. 74 00:06:37,460 --> 00:06:40,930 I don't want you to use those. For the next couple weeks. 75 00:06:40,930 --> 00:06:45,545 In order to get at the insides of lists, in order to take lists apart, and we want 76 00:06:45,545 --> 00:06:51,022 you to use first and rest. So using only first and rest how do I get 77 00:06:51,022 --> 00:06:55,230 at the second element of L2? Well if, if I call first as the first 78 00:06:55,230 --> 00:06:59,390 thing I do I'm in trouble. because I'll just get temp. 79 00:06:59,390 --> 00:07:02,540 But what I do actually is I take rest of L2. 80 00:07:02,540 --> 00:07:06,320 Now that's going to give me cons nine, cons ten empty. 81 00:07:06,320 --> 00:07:14,715 And once I have rest of L2, then the first of that, is the second thing in L2. 82 00:07:14,715 --> 00:07:18,920 The way to read this is, first of rest of l2. 83 00:07:18,920 --> 00:07:23,687 So rest of l2 is that. It would be the first of that, which is 84 00:07:23,687 --> 00:07:26,759 9. How do I get the third element? 85 00:07:26,759 --> 00:07:31,180 You just do the same trick again. You say first a rest. 86 00:07:31,180 --> 00:07:36,478 The rest of L2. Now that would get tedious if you wanted 87 00:07:36,478 --> 00:07:39,280 to get the twenty third element of a list. 88 00:07:39,280 --> 00:07:42,870 And what we'll see, starting in the next lecture is that we do it a different way. 89 00:07:42,870 --> 00:07:45,260 So let's see, I have cons for constructing lists. 90 00:07:45,260 --> 00:07:47,870 I have first and rest for taking lists apart. 91 00:07:47,870 --> 00:07:51,302 There's one more primitive that dsl gives me for working with lists, and that's 92 00:07:51,302 --> 00:07:54,823 called empty question mark. It's a predicate cause it's name ends in 93 00:07:54,823 --> 00:07:57,876 question mark. And what happens is the empty question 94 00:07:57,876 --> 00:08:01,948 mark of empty. Produces - let me comment these things 95 00:08:01,948 --> 00:08:07,359 out so we won't get confused here. Empty? 96 00:08:07,359 --> 00:08:11,430 of empty produces true. And empty? 97 00:08:11,430 --> 00:08:17,070 of a list that isn't empty or in fact of anything at all produces false. 98 00:08:17,070 --> 00:08:22,662 You can also say if you want empty? of one but you're not going to say that 99 00:08:22,662 --> 00:08:28,014 As often. We'll often want to know is the list that 100 00:08:28,014 --> 00:08:33,220 we're holding here empty? So there you go, there's the primitives 101 00:08:33,220 --> 00:08:38,089 for constructing and operating on lists that are part of the DSL language.