1 00:00:07,300 --> 00:00:08,570 Okay. In this video, I'm going to work through 2 00:00:08,570 --> 00:00:13,150 the design of a Valid Board. And as I said, this is paradoxically the 3 00:00:13,150 --> 00:00:17,530 hardest function in the whole program. But by working systematically, I'm 4 00:00:17,530 --> 00:00:21,682 going to get there bit by bit. The first thing I'm going to do is well, 5 00:00:21,682 --> 00:00:23,946 hmm. I'm going to start to write a template. 6 00:00:23,946 --> 00:00:30,030 And what am I going to put in this template? 7 00:00:30,030 --> 00:00:36,960 Well I have to produce true if no unit on the board has the same value twice. 8 00:00:36,960 --> 00:00:39,280 In other words I'm going to produce false. 9 00:00:39,280 --> 00:00:42,530 What I showed you in the last video, what I reminded you of in the last video is 10 00:00:42,530 --> 00:00:48,130 that there is this constant here units, which is the list of all the units. 11 00:00:49,370 --> 00:00:54,928 So really what I'd like to be able to do here is operate on that list of units to 12 00:00:54,928 --> 00:01:01,910 make sure that all of them are valid. So I sort of wish that I could template 13 00:01:01,910 --> 00:01:04,602 this somehow as doing something on the list of units. 14 00:01:04,602 --> 00:01:10,990 Now this is a slightly different template from before, but we can always put 15 00:01:10,990 --> 00:01:14,380 constants into a template to say that we want to operate on those constants. 16 00:01:15,740 --> 00:01:20,500 And now I'll just go directly to wishing that I could say something. 17 00:01:20,500 --> 00:01:24,360 And what I wish I could say here, is that I wish I could say that all these units 18 00:01:24,360 --> 00:01:30,611 are valid. So I'm going to write a wish-list entry 19 00:01:30,611 --> 00:01:33,770 for that. And I'm going to do it inside a local, 20 00:01:33,770 --> 00:01:35,910 'cuz I think there's going to be several of these upper functions. 21 00:01:35,910 --> 00:01:38,590 I don't have to do this in local. I can do this at top level. 22 00:01:38,590 --> 00:01:40,860 I'm just going to do it in a local to show you that I can. 23 00:01:40,860 --> 00:01:51,552 I'll say that valid units is a function I wish I had. 24 00:01:51,552 --> 00:01:56,587 In it well what's its signature going to be? 25 00:01:56,587 --> 00:02:03,119 Well I'm giving it a list of unit, because that's what units is. 26 00:02:03,119 --> 00:02:08,080 Units is a list of unit. And, I want it to give me back a boolean. 27 00:02:08,080 --> 00:02:12,121 I want it to give me back true if all the units are valid. 28 00:02:12,121 --> 00:02:17,610 So that's a reasonable stub for it, and now I've made some progress. 29 00:02:17,610 --> 00:02:21,720 Because I've said that validating the entire board means validating all the 30 00:02:21,720 --> 00:02:24,490 units. Let's keep going. 31 00:02:24,490 --> 00:02:29,170 How am I going to template valid units? What goes here? 32 00:02:29,170 --> 00:02:33,320 Well, it's dot, dot, dot lou. That's the template for starters. 33 00:02:33,320 --> 00:02:36,499 But how do I template it? Do I template it according to list? 34 00:02:37,920 --> 00:02:43,350 Operating on all, the units in this list of units. 35 00:02:43,350 --> 00:02:47,290 I could template it that way. But what I'm going to remember here, is 36 00:02:47,290 --> 00:02:51,170 that this needs to make sure that every single unit, in the list of units, is 37 00:02:51,170 --> 00:02:54,272 valid. And that's an andmap. 38 00:02:54,272 --> 00:02:59,205 That's an andmap. So I'm going to template it as a call to 39 00:02:59,205 --> 00:03:06,637 andmap. Now I've templated it as a call to 40 00:03:06,637 --> 00:03:10,790 andmap. I need to fit in the dots. 41 00:03:10,790 --> 00:03:18,490 Well, in andmap, the dots in this case, the signature of the dots, this function 42 00:03:18,490 --> 00:03:23,290 right here. The function that we'd stick in right 43 00:03:23,290 --> 00:03:28,760 here has to have the signature, unit to Boolean. 44 00:03:28,760 --> 00:03:33,520 Because I'm calling andmap with a listed unit, and andmap is going to call this 45 00:03:33,520 --> 00:03:36,270 function with each of the units in turn and the function has to produce a 46 00:03:36,270 --> 00:03:39,710 Boolean, so here what we need is a function. 47 00:03:39,710 --> 00:03:45,137 It checks whether an individual unit is valid, well we don't have one, but let's 48 00:03:45,137 --> 00:03:47,633 wish for one. [NOISE]. 49 00:03:47,633 --> 00:04:03,271 I'll wish for it right here. That's the stub for it, and its signature 50 00:04:03,271 --> 00:04:12,020 is that it consumes a unit. I'm going to write this this way just for 51 00:04:12,020 --> 00:04:15,980 fun. Unit to Boolean. 52 00:04:15,980 --> 00:04:19,230 So this function, let me get rid of this blank line here. 53 00:04:19,230 --> 00:04:26,540 The first function, valid units, consumes a list of unit and produces a Boolean 54 00:04:26,540 --> 00:04:30,787 saying whether all of them are valid. The second function I wished for, valid 55 00:04:30,787 --> 00:04:35,603 unit consumes an individual unit that produces a Boolean saying whether it's 56 00:04:35,603 --> 00:04:42,675 valid. How am I going to template this? 57 00:04:42,675 --> 00:04:53,350 Well, I could go look at what a unit is. A unit is a list of pause. 58 00:04:55,280 --> 00:05:08,028 Hey a unit is a list of pause. But what does it mean for a unit to be 59 00:05:08,028 --> 00:05:12,360 valid? It means that the unit does not have the 60 00:05:12,360 --> 00:05:17,110 same value twice. Here's an example that uses the unit for 61 00:05:17,110 --> 00:05:23,160 the third row of a board. Here's the unit, that lists all the 62 00:05:23,160 --> 00:05:27,910 positions of the third row, and here's the actual board and its third row. 63 00:05:27,910 --> 00:05:33,924 If I used that unit to read all these values, to read the contents of the third 64 00:05:33,924 --> 00:05:35,940 row. I would get a list like this. 65 00:05:35,940 --> 00:05:41,636 And I need to throw out all the falses, because you are allowed to have more than 66 00:05:41,636 --> 00:05:45,107 one false. If I throw out all the falses, now I just 67 00:05:45,107 --> 00:05:52,038 have the values in that row. And if there's no duplicates there, the 68 00:05:52,038 --> 00:05:55,192 unit's valid. Let's see. 69 00:05:55,192 --> 00:06:00,870 I've gotta read out the unit. I've gotta get rid of the falses or keep 70 00:06:00,870 --> 00:06:05,140 only the numbers, and I've gotta make sure there's no duplicates. 71 00:06:05,140 --> 00:06:09,670 That's three distinct operations on, on the entire value in each step. 72 00:06:09,670 --> 00:06:13,730 That's a function composition. Let's write this, let's template this as 73 00:06:13,730 --> 00:06:15,570 a function composition. Let's see. 74 00:06:15,570 --> 00:06:28,000 The first thing we need to do is read the unit, U, and once we've got the unit, we 75 00:06:28,000 --> 00:06:31,630 need to keep only the values. Right. 76 00:06:31,630 --> 00:06:36,860 I could, I could wish for a function called get rid of the falses. 77 00:06:36,860 --> 00:06:41,436 It would be the same. But I'm going to wish for a function 78 00:06:41,436 --> 00:06:47,410 called keep only the values. And once we've kept only the values, we 79 00:06:47,410 --> 00:06:49,110 need to make sure that there are no duplicates. 80 00:06:49,110 --> 00:06:51,550 We need to ask, are, make sure there's no duplicates. 81 00:06:51,550 --> 00:07:01,750 So that's a function composition wish. And it might look a little more clear if 82 00:07:01,750 --> 00:07:10,010 we do the line breaking like this. I wish now for three functions. 83 00:07:10,010 --> 00:07:14,922 Let's wait the way entry for them define read unit of u. 84 00:07:14,922 --> 00:07:20,150 Okay. Now that's going to produce a list of 85 00:07:20,150 --> 00:07:25,950 values or false. So, we'll stub is as producing empty, and 86 00:07:25,950 --> 00:07:34,760 this goes from unit to list of val or false. 87 00:07:34,760 --> 00:07:51,760 And keep only values. Keep only Values, of one of these lists 88 00:07:51,760 --> 00:07:58,590 of value or false. Is going to produce a list of just the 89 00:07:58,590 --> 00:08:08,864 values. So this consumes list of val or false, 90 00:08:08,864 --> 00:08:20,142 and produces list of val, and no duplicates. 91 00:08:20,142 --> 00:08:33,879 This consumes a list of val, and it produces a Boolean. 92 00:08:33,879 --> 00:08:45,338 [SOUND] And say whether there's no duplicates in there. 93 00:08:45,338 --> 00:08:47,652 So I'm just wishing away. Well, let's see. 94 00:08:47,652 --> 00:08:57,509 Read unit. Read unit consumes a unit, and, fix my 95 00:08:57,509 --> 00:09:05,730 line-breaking here a little bit, and how am I going to template this? 96 00:09:05,730 --> 00:09:12,705 It consumes a unit; and remember, a unit is a list of pause. 97 00:09:12,705 --> 00:09:23,180 And it's gotta read all of those values. So, I could template this according to 98 00:09:23,180 --> 00:09:29,450 list, because a unit is a list of pos. But what I've gotta do for every single 99 00:09:29,450 --> 00:09:32,510 one of those pos's is read its value out of the board. 100 00:09:34,180 --> 00:09:37,365 Read, read from the board the value of that position. 101 00:09:37,365 --> 00:09:42,850 I've got to do it for every single pause in the unit. 102 00:09:45,410 --> 00:09:49,290 This is a map. I'm going to template it as a map. 103 00:09:49,290 --> 00:09:57,146 I'm going to map something over the unit. Now what am I going to map over the unit? 104 00:09:57,146 --> 00:10:10,406 It's some function that consumes a pos and reads that position from the board. 105 00:10:10,406 --> 00:10:20,521 Lets wish for that. This is a function that consumes a pos 106 00:10:20,521 --> 00:10:25,740 and produces what's sitting in the board at that pos. 107 00:10:25,740 --> 00:10:28,460 So it's going to produce either a value or false. 108 00:10:28,460 --> 00:10:35,790 How am I going to template that? Well, let's see. 109 00:10:35,790 --> 00:10:47,587 It's definitely got the pos to work with. And reminding ourselves what a pos is, go 110 00:10:47,587 --> 00:10:59,910 all the way up here. A pos is a natural from zero to 80. 111 00:10:59,910 --> 00:11:03,731 So if I template this according to the template of that natural [UNKNOWN] 112 00:11:03,731 --> 00:11:08,984 non-distinct. I put dot, dot, dot p. 113 00:11:08,984 --> 00:11:16,980 Now, what does this function need to do? Okay, it needs to, we can put it right 114 00:11:16,980 --> 00:11:26,100 here, if we want. Produce contents of board, and by board I 115 00:11:26,100 --> 00:11:30,020 mean this board here, the board right at the top. 116 00:11:30,020 --> 00:11:37,206 Produce contents of the board at p. How do I do that? 117 00:11:37,206 --> 00:11:44,758 Oh, well that's easy remember we have this primitive way down here, read 118 00:11:44,758 --> 00:11:49,110 square. That produces contents of a board, 119 00:11:49,110 --> 00:11:54,358 produces contents of a board at a given position p. 120 00:11:54,358 --> 00:11:59,275 Let's remember the order of arguments to it. 121 00:11:59,275 --> 00:12:02,740 It should be board and then position, and it is. 122 00:12:02,740 --> 00:12:17,790 So this is just read-square board and p. Hey, I finish the function without 123 00:12:17,790 --> 00:12:19,710 wishing for another function, that was kind of great. 124 00:12:22,540 --> 00:12:26,040 All these ones up here are done, ooh that doesn't belong a blank line there. 125 00:12:26,040 --> 00:12:32,250 All these ones up here are done. These are the only ones that I still 126 00:12:32,250 --> 00:12:35,850 haven't completed. I could have maybe been putting bang, 127 00:12:35,850 --> 00:12:37,875 bang, bangs in here to keep them more clear. 128 00:12:37,875 --> 00:12:44,115 Let's see, keep all the values. This consumes the list of values or false 129 00:12:44,115 --> 00:12:50,879 and it produces a list of value. How am I going to template that? 130 00:12:50,879 --> 00:12:58,091 Well, this is a filter of some sort. Filter dot, dot, dot, l o v f. 131 00:12:58,091 --> 00:13:10,750 I'm going to template that that way. Now I need to remember what a value is. 132 00:13:10,750 --> 00:13:18,980 Let me go look. A value is a natural, from one to nine. 133 00:13:18,980 --> 00:13:23,285 So let's see, go back down here to keep only values. 134 00:13:23,285 --> 00:13:29,795 I'm consuming a list of value or false, and I need to produce just the values. 135 00:13:29,795 --> 00:13:34,980 And values are naturals from one to nine. Oh, this is easy. 136 00:13:34,980 --> 00:13:41,449 I'll just filter this with number question mark. 137 00:13:41,449 --> 00:13:46,250 Number question mark will produce false every time it's given false, and then it 138 00:13:46,250 --> 00:13:50,020 will produce true every time it's given a natural from one to nine. 139 00:13:50,020 --> 00:13:54,822 So this will keep just a number. Seems like I'm getting close. 140 00:13:54,822 --> 00:14:00,440 What about no duplicate? But see, no duplicates consumes list of 141 00:14:00,440 --> 00:14:07,140 value, and it needs to produce true. Let's take a moment to write out its 142 00:14:07,140 --> 00:14:12,910 purpose. [SOUND] Reduce true if no value, in l o v 143 00:14:12,910 --> 00:14:17,740 appears twice. How am I going to template that? 144 00:14:17,740 --> 00:14:25,882 Well to see whether something appears twice in a list, I kind of have to go 145 00:14:25,882 --> 00:14:34,024 through every element in the list. And make sure that it doesn't appear 146 00:14:34,024 --> 00:14:42,740 anywhere in the rest of the list, right? Because if I check every element and make 147 00:14:42,740 --> 00:14:58,510 sure that it doesn't appear again later in the list, then I'll know there's not 148 00:14:58,510 --> 00:15:01,820 duplicates. I don't need to know whether something is 149 00:15:01,820 --> 00:15:06,110 duplicated twice. I don't need to know whether something, I 150 00:15:06,110 --> 00:15:09,000 don't need to ask the question, well, does this thing appear earlier in the 151 00:15:09,000 --> 00:15:12,050 list. If I just ask the question, hey for every 152 00:15:12,050 --> 00:15:18,040 element of the list does it appear again later, I'll find all the duplicates. 153 00:15:18,040 --> 00:15:23,280 Notice what I just did here. I just did the example step of the htdf 154 00:15:23,280 --> 00:15:27,290 recipe. I'm not writing check expects, because 155 00:15:27,290 --> 00:15:33,950 I'm not defining a function at top level. And I'm not even writing a complete call 156 00:15:33,950 --> 00:15:37,090 to no duplicates. But what I'm doing is I'm writing down 157 00:15:37,090 --> 00:15:42,370 examples of data that no duplicates is going to have to consume, and using those 158 00:15:42,370 --> 00:15:46,460 examples to help me figure out what to do. 159 00:15:46,460 --> 00:15:51,070 Remember what I said about the recipe, you don't always have to use all of it. 160 00:15:52,340 --> 00:15:56,720 But here this function got a little hard on me, and so I started using a bit more 161 00:15:56,720 --> 00:15:58,610 of the recipe. I pulled in the examples. 162 00:16:00,550 --> 00:16:02,755 I've been using the signature all the way through here. 163 00:16:02,755 --> 00:16:07,500 I use the purpose a couple of times. Here I'm using the signature purpose and 164 00:16:07,500 --> 00:16:09,910 some examples. Even though I'm kind of just writing the 165 00:16:09,910 --> 00:16:13,760 examples on a piece of scratch paper. So it seems like I need to go through the 166 00:16:13,760 --> 00:16:16,480 whole list and I need to go through the whole list doing something a little 167 00:16:16,480 --> 00:16:20,850 different than map or filter or folder do, so I'm going to have to use the full 168 00:16:20,850 --> 00:16:29,072 on list template here. Cond empty l o v something. 169 00:16:29,072 --> 00:16:37,959 Else, oops, let's put this purpose up here, where it will do us more good, else 170 00:16:37,959 --> 00:16:50,274 dot, dot, dot something with first of l o v, and no duplicates of rest of l o v. 171 00:16:50,274 --> 00:16:56,582 I'm just writing the list of template from memory at this point. 172 00:16:56,582 --> 00:17:04,582 Okay, let's fill in the template. Let's see. 173 00:17:04,582 --> 00:17:11,750 If I get to the end of the list. And I haven't found a duplicate yet. 174 00:17:11,750 --> 00:17:22,220 Then that means there are no duplicates. Yay, fantastic, let's produce true. 175 00:17:24,810 --> 00:17:29,800 Otherwise, hm. What I need to ask somehow is I need to 176 00:17:29,800 --> 00:17:37,460 ask the question, hey does this thing appear in the rest of the list? 177 00:17:37,460 --> 00:17:42,270 Does the first appear in the rest? I need to somehow ask that question. 178 00:17:42,270 --> 00:17:47,690 There's a specific question I need to ask there, does the first appear in the rest? 179 00:17:47,690 --> 00:17:51,013 Now, let's see. The first will be a number, but the rest 180 00:17:51,013 --> 00:17:53,872 will be a list, so I'm operating on a list here. 181 00:17:55,160 --> 00:17:57,940 So the operating on arbitrary size data rule comes in. 182 00:17:57,940 --> 00:18:03,762 This dot, dot, dot, has to be a function. And we've seen functions like this before 183 00:18:03,762 --> 00:18:09,218 earlier in this course, we wrote some functions that we gave them names like 184 00:18:09,218 --> 00:18:13,360 contains. To check whether a string appeared in a 185 00:18:13,360 --> 00:18:18,955 list of string. Turns out there's a built in function 186 00:18:18,955 --> 00:18:24,070 like this you can use in dsl and isl called member. 187 00:18:24,070 --> 00:18:26,890 Member is just the built in version of contain... 188 00:18:26,890 --> 00:18:32,000 It tells us whether its first argument appears in the list that's the second 189 00:18:32,000 --> 00:18:35,320 argument. So there's the question, the question is 190 00:18:35,320 --> 00:18:36,903 eh, if I find the first thing in the rest, oh, there's an if here, for sure. 191 00:18:36,903 --> 00:18:40,550 So, if I find the first thing in the rest, then that's bad. 192 00:18:40,550 --> 00:18:52,550 That means there was a duplicate. So since I gave this function a negative 193 00:18:52,550 --> 00:18:57,250 name, I gotta produce false. The answer to the question, are there no 194 00:18:57,250 --> 00:19:01,580 duplicates, is false. I've just found a duplicate. 195 00:19:01,580 --> 00:19:08,800 Otherwise, we do the natural reccursion. Let's see our parens balanced here. 196 00:19:08,800 --> 00:19:22,304 Give it a go. All 20 tests passed. 197 00:19:22,304 --> 00:19:28,360 And I believe, have I commented out the board tests? 198 00:19:28,360 --> 00:19:32,850 Yeah, these board tests are uncommented, so all the tests are now passing. 199 00:19:32,850 --> 00:19:42,270 So look, that function was a little bit complicated, and I walked you through the 200 00:19:42,270 --> 00:19:46,500 I made no mistakes version of it. There's no way you were going to get to 201 00:19:46,500 --> 00:19:49,252 the design of this function just as quickly as I did. 202 00:19:49,252 --> 00:19:55,230 There's no way you were going to get to the design of this function as quickly as 203 00:19:55,230 --> 00:19:58,620 I just did it. So, don't be discouraged if you're 204 00:19:58,620 --> 00:20:00,740 sitting there going. There's no way I would have done that as 205 00:20:00,740 --> 00:20:04,710 quickly. That's not my goal. 206 00:20:04,710 --> 00:20:07,230 What I would like you to be able to do is to see how. 207 00:20:07,230 --> 00:20:14,700 All I did to produce it was follow the design recipes that we've learned in this 208 00:20:14,700 --> 00:20:18,960 course. Now, there's some cases where I chose to 209 00:20:18,960 --> 00:20:21,655 template according to andmap, for example. 210 00:20:21,655 --> 00:20:26,170 And you might have chosen the template according to list of unit. 211 00:20:26,170 --> 00:20:28,300 That would be fine. You'd get there, too. 212 00:20:28,300 --> 00:20:32,820 It would take you a little bit longer to get there 'cuz andmap is, is, is quicker 213 00:20:32,820 --> 00:20:38,856 than, basically doing a concrete version of andmap, but you would have gotten 214 00:20:38,856 --> 00:20:41,250 there. You might not have templated according to 215 00:20:41,250 --> 00:20:45,390 a three function composition right away. That was going to cause you a bit more 216 00:20:45,390 --> 00:20:49,530 trouble but you would have gotten there. What I need you to be able to do at this 217 00:20:49,530 --> 00:20:56,370 point is go back through this and see that this was a reasonable scenario, and 218 00:20:56,370 --> 00:21:00,550 see why I made each choice I made at each point. 219 00:21:00,550 --> 00:21:04,080 But this was a hard function. It's the hardest single function we've 220 00:21:04,080 --> 00:21:08,370 seen so far in this course. In fact it didn't end up being a single 221 00:21:08,370 --> 00:21:10,960 function. It ended up having six helpers. 222 00:21:10,960 --> 00:21:16,610 The key point is that the method we have been learning really did help me get 223 00:21:16,610 --> 00:21:19,280 there. So go through this again and then we'll 224 00:21:19,280 --> 00:21:21,467 give you a problem to work on.