1 00:00:06,140 --> 00:00:09,312 In the next few videos, we're going to look at a more complex form of data than 2 00:00:09,312 --> 00:00:13,830 we've seen before. This data involves something called 3 00:00:13,830 --> 00:00:17,550 reference, and it comes up when the information we're trying to represent 4 00:00:17,550 --> 00:00:24,114 naturally has different related parts. Now that only happens in problems that 5 00:00:24,114 --> 00:00:26,550 are more complex than the ones we've seen so far. 6 00:00:27,560 --> 00:00:31,070 So, in order to motivate this, I have to be working on a more complex problem and 7 00:00:31,070 --> 00:00:34,710 a problem that will take several videos to solve. 8 00:00:36,410 --> 00:00:39,696 Now, of course when I do that, there'll be parts of this problem, a number of 9 00:00:39,696 --> 00:00:43,087 parts of this problem that are quite familiar. 10 00:00:43,087 --> 00:00:45,510 That only take things that we've seen before. 11 00:00:46,690 --> 00:00:50,844 So, as always when that's the situation, that's a good place to stop the video and 12 00:00:50,844 --> 00:00:54,643 work ahead. In fact, to really encourage that this 13 00:00:54,643 --> 00:01:00,270 time, there will be pauses in the video, breaks in the video where I jump ahead. 14 00:01:01,550 --> 00:01:04,345 I won't actually work through some of the stuff that you've seen now many times 15 00:01:04,345 --> 00:01:07,254 before. That's a place for you to do that 16 00:01:07,254 --> 00:01:12,390 yourself and then see where you are when the video restarts. 17 00:01:12,390 --> 00:01:14,917 Okay, the problem is in tuition graph starter. 18 00:01:14,917 --> 00:01:18,669 What's going on here is that we're trying to design a program that can produce bar 19 00:01:18,669 --> 00:01:23,525 charts of different kinds of information. The way I've got the problem set up is 20 00:01:23,525 --> 00:01:27,197 that it's supposed to produce a bar chart of tuition information for an arbitrary 21 00:01:27,197 --> 00:01:31,341 number of schools. We're saying that Eva has to decide where 22 00:01:31,341 --> 00:01:34,581 to go to University, and she wants to make a plot of the different tuition 23 00:01:34,581 --> 00:01:40,100 costs for Universities. So, it's a three part problem. 24 00:01:40,100 --> 00:01:43,340 First, we have to design a data definition to represent the information 25 00:01:43,340 --> 00:01:46,666 about the tuition at the different Universities. 26 00:01:46,666 --> 00:01:49,960 Then we have to design a function that's going to consume a list like that and 27 00:01:49,960 --> 00:01:54,632 produce a bar chart like this one here. Finally, we have to design a function 28 00:01:54,632 --> 00:01:57,710 that's going to consume a list of tuition information at the different 29 00:01:57,710 --> 00:02:02,280 universities, and produce the school that has the lowest tuition. 30 00:02:02,280 --> 00:02:05,584 What I'm going to do now is that even though this isn't a word program, I can 31 00:02:05,584 --> 00:02:09,930 see that there's some constants here related to the drawing. 32 00:02:09,930 --> 00:02:14,220 Things like the color of the bars and the size of the font. 33 00:02:14,220 --> 00:02:19,600 And so, we'll do a little bit of constant analysis and defining some contants now. 34 00:02:19,600 --> 00:02:22,070 So, why don't you stop the video and you do that too and when you're done restart 35 00:02:22,070 --> 00:02:25,350 the video, and you can compare what you've done to what I've done. 36 00:02:28,700 --> 00:02:31,886 Now I've completed a little bit of constant analysis and defining some 37 00:02:31,886 --> 00:02:34,628 constants. And I should say first, that if you 38 00:02:34,628 --> 00:02:38,084 didn't see right away that the defining constants was a good thing to do here, 39 00:02:38,084 --> 00:02:42,376 that's completely fine. Sometimes you identify constants up 40 00:02:42,376 --> 00:02:45,940 front, sometimes you realize later that you'll need them. 41 00:02:45,940 --> 00:02:48,830 If you didn't see that right away, that's fine. 42 00:02:48,830 --> 00:02:52,504 Let me show you what I've done. I'm in a different version of the file 43 00:02:52,504 --> 00:02:56,166 now, tuition graph V1. I added require 2htdp/Image at the top 44 00:02:56,166 --> 00:02:59,530 because I knew I was going to be doing some drawing. 45 00:02:59,530 --> 00:03:02,530 I've made it part of the file for constants, and I said you know, this font 46 00:03:02,530 --> 00:03:05,630 size here that we're going to be drawing the name of the schools in, that looks 47 00:03:05,630 --> 00:03:09,540 like a good constant. By defining a constant for it will be 48 00:03:09,540 --> 00:03:13,743 easier for me to change later. And the font color similarly I made that 49 00:03:13,743 --> 00:03:18,102 black. And I also realized that there would have 50 00:03:18,102 --> 00:03:21,698 to be kind of a scaling factor, because these tuitions are going to be numbers 51 00:03:21,698 --> 00:03:25,707 like $20,000. And I'm pretty sure I don't want to make 52 00:03:25,707 --> 00:03:29,202 the graph 20,000 pixels high. That's going to be kind of a very high 53 00:03:29,202 --> 00:03:31,070 graph. It won't fit on the screen or the piece 54 00:03:31,070 --> 00:03:34,862 of paper, or anything. So, I invented a concept that I'm calling 55 00:03:34,862 --> 00:03:38,960 the Y scale, or I could've called it the Y scale factor or something. 56 00:03:38,960 --> 00:03:42,680 But it's basically how much I'm going to divide the dollars by to convert it to 57 00:03:42,680 --> 00:03:46,910 the height of the bar, and I just guessed one over 200. 58 00:03:46,910 --> 00:03:49,088 Maybe that'll end up being right, maybe it won't. 59 00:03:49,088 --> 00:03:52,347 We'll see later. The bars have to have a width, I just 60 00:03:52,347 --> 00:03:56,726 guessed that 30 pixels will look good. And the bars have to have a color, I just 61 00:03:56,726 --> 00:04:01,362 guessed that light blue would look good. Remember, the reason we give names to 62 00:04:01,362 --> 00:04:04,794 these constants is to make it easy to get the program going quickly, then you can 63 00:04:04,794 --> 00:04:09,700 adjust them to look a little bit better. So, that's the constants. 64 00:04:10,720 --> 00:04:13,965 The next thing I have to do is the data definitions for representing the 65 00:04:13,965 --> 00:04:19,125 information in this problem. Remember, the information that we have to 66 00:04:19,125 --> 00:04:22,345 represent is for an arbitrary number of schools. 67 00:04:22,345 --> 00:04:26,690 We need to know for each school, what it's name is and what it's tuition is. 68 00:04:26,690 --> 00:04:30,982 Now, what makes this problem different is we're going to have two data definitions. 69 00:04:30,982 --> 00:04:34,825 There's going to be one compound data definition called School, and that's 70 00:04:34,825 --> 00:04:39,780 going to be used to represent information about an individual school. 71 00:04:41,410 --> 00:04:45,006 And then there's going to be an arbitrary size data definition called List of 72 00:04:45,006 --> 00:04:49,985 School, which will represent an arbitrary number of those school units. 73 00:04:49,985 --> 00:04:54,465 And what's going to happen there is the second data definition, list of school, 74 00:04:54,465 --> 00:04:59,090 is going to refer to the first data definition, school. 75 00:05:00,250 --> 00:05:03,500 And that's going to carry through the entire problem. 76 00:05:03,500 --> 00:05:06,293 So, there will be what's called a reference relationship in the type 77 00:05:06,293 --> 00:05:08,828 comment. There will be what's called a natural 78 00:05:08,828 --> 00:05:12,840 helper in the templates. And in the final function, there will be 79 00:05:12,840 --> 00:05:16,804 a helper function call. We've seen this before, it's a theme of 80 00:05:16,804 --> 00:05:20,234 this part of the course. The structure of the information 81 00:05:20,234 --> 00:05:23,066 determines the structure of the data, determines the structure of the 82 00:05:23,066 --> 00:05:26,510 templates, determines the structure of the functions. 83 00:05:28,920 --> 00:05:31,880 So now, let's go look at how this plays out in the code. 84 00:05:31,880 --> 00:05:36,168 I'm in tuition graph V2, and I've started the data definition, but I've saved the 85 00:05:36,168 --> 00:05:42,094 most interesting part to do now. In terms of the compound information 86 00:05:42,094 --> 00:05:45,604 about the school, that's a compound data definition, like the ones we've seen 87 00:05:45,604 --> 00:05:49,484 before. I defined a structure called school with 88 00:05:49,484 --> 00:05:55,052 two fields, name and tuition. And I said that a school is a make school 89 00:05:55,052 --> 00:05:58,600 where name is a string and tuition is a natural. 90 00:05:59,610 --> 00:06:02,850 And I'm just saying here that name is the school's name and tuition is the 91 00:06:02,850 --> 00:06:06,190 international students tuition in US dollars. 92 00:06:06,190 --> 00:06:09,916 Remember we like to put units for numbers in interpretations, and I just decided on 93 00:06:09,916 --> 00:06:12,950 US dollars. You can use whatever currency you want. 94 00:06:14,820 --> 00:06:18,468 And then, I just put some examples, I said school one is a school called school 95 00:06:18,468 --> 00:06:21,931 one. And it has a tuition of $27797. 96 00:06:21,931 --> 00:06:29,202 And school two is $23,300, and school three is $20,500. 97 00:06:29,202 --> 00:06:35,950 The template for school is straight forward, it's compound of two fields. 98 00:06:35,950 --> 00:06:39,320 Both fields are primitive types, string and natural. 99 00:06:39,320 --> 00:06:43,180 So, the template just ends up looking like that. 100 00:06:43,180 --> 00:06:47,950 Now, the list of school data definition starts out just like we've seen before. 101 00:06:47,950 --> 00:06:52,724 I'll say that list of school is one of either empty for the base case, or cons 102 00:06:52,724 --> 00:06:58,225 something list of school, for the self reference case. 103 00:06:58,225 --> 00:07:02,912 But the question is what's the something? And for the something here, rather than 104 00:07:02,912 --> 00:07:06,098 putting a primitive type, I've put school, because that's what list of 105 00:07:06,098 --> 00:07:10,708 school really needs it be. It needs to be a list of representations 106 00:07:10,708 --> 00:07:14,081 of schools. So, that in this list, I'll have an 107 00:07:14,081 --> 00:07:18,865 arbitrary number of schools. And then for each school, I'll have its 108 00:07:18,865 --> 00:07:23,823 name and its tuition. And so, this type comment has something 109 00:07:23,823 --> 00:07:27,042 quite new. And it's really the new thing in this 110 00:07:27,042 --> 00:07:30,221 whole problem. In addition to the self reference 111 00:07:30,221 --> 00:07:36,090 relationship, it also has what we want to call a reference relationship. 112 00:07:36,090 --> 00:07:40,750 It refers right here to a non-primitive type. 113 00:07:40,750 --> 00:07:44,718 And the way we're going to draw that is with an arrow, like the arrow we used for 114 00:07:44,718 --> 00:07:50,540 self reference, but we're going to label it with an R for reference. 115 00:07:50,540 --> 00:07:53,960 That picture of the two type comments with the two arrows is going to define 116 00:07:53,960 --> 00:07:57,580 the structure of the entire rest of this problem. 117 00:07:58,690 --> 00:08:01,010 Let me show you how that starts happening in the template. 118 00:08:01,010 --> 00:08:10,630 Define fn-for-los los template rules used. 119 00:08:10,630 --> 00:08:14,654 And it starts out pretty normally, I'll go, I'll speed things up a bit here. 120 00:08:14,654 --> 00:08:20,842 [BLANK_AUDIO] 121 00:08:20,842 --> 00:08:45,120 Now here's where it gets a little bit different. 122 00:08:45,120 --> 00:08:49,817 We've already seen in the previous examples, that we know that rest of los 123 00:08:49,817 --> 00:08:54,206 is going to be a value of type list of school, and that's going to cause us to 124 00:08:54,206 --> 00:09:01,290 use the self reference rule. I'm going to skip a line here. 125 00:09:01,290 --> 00:09:04,135 That's going to cause us to use the self reference rule. 126 00:09:04,135 --> 00:09:17,648 And the self reference rule makes us put a natural recursion right here. 127 00:09:17,648 --> 00:09:21,420 But remember, this type comment has a second arrow /g. 128 00:09:21,420 --> 00:09:25,380 We know that the type of first los is going to be school. 129 00:09:25,380 --> 00:09:31,740 And school is a non-primitive type, that's why we have the arrow labelled r. 130 00:09:32,980 --> 00:09:38,425 And that's going to cause us to use what's called the reference rule. 131 00:09:38,425 --> 00:09:45,050 And the reference rule says that first los is school, it's a non-primitive type. 132 00:09:45,050 --> 00:09:47,804 So, what we're going to do right here, we're going to put in a call to the 133 00:09:47,804 --> 00:09:50,781 template function for the referred to type. 134 00:09:51,790 --> 00:09:54,698 That picture is a little hard to understand like that. 135 00:09:54,698 --> 00:09:56,960 So, let me just rearrange it a little bit. 136 00:09:56,960 --> 00:10:00,132 And what I've done in this picture is I've put the two type comments next to 137 00:10:00,132 --> 00:10:03,780 each other, and the two templates next to each other. 138 00:10:03,780 --> 00:10:07,686 And I think that when I arrange it like this, you can see what's going on here a 139 00:10:07,686 --> 00:10:12,730 little bit better. In the two tied comments: we have the 140 00:10:12,730 --> 00:10:15,655 self reference from earlier this week, and we have the reference which we just 141 00:10:15,655 --> 00:10:22,074 saw today for the first time. And in the templates, the soft reference 142 00:10:22,074 --> 00:10:26,232 produces a natural recursion, and the reference produces what we're going to 143 00:10:26,232 --> 00:10:31,044 call a natural helper. When we design a function that consumes a 144 00:10:31,044 --> 00:10:34,704 list of school, we'll see what the presence of this natural helper in the 145 00:10:34,704 --> 00:10:38,840 template does to the design of that function. [BLANK_AUDIO]