1 00:00:08,060 --> 00:00:12,566 In this video, I'm going to design another function operating on element. 2 00:00:12,566 --> 00:00:18,770 Remember that Element and ListOfElement are mutually referential types. 3 00:00:18,770 --> 00:00:22,268 And so that means designing one function is actually going to end up designing two 4 00:00:22,268 --> 00:00:25,119 of them. I mean, fs2-v2.racket and if I scroll 5 00:00:25,119 --> 00:00:30,582 down here to the problem, here it is. Design a function that consumes element 6 00:00:30,582 --> 00:00:37,112 and produces a list of the names of all the elements in the tree. 7 00:00:38,610 --> 00:00:44,748 So I know right away consumes element and I need to know what list of names means, 8 00:00:44,748 --> 00:00:50,421 so I go back up to the element data definition, and let's see for an element 9 00:00:50,421 --> 00:01:01,234 the name is a string. So this is going to produce ListOfString 10 00:01:01,234 --> 00:01:07,549 and of course there'll be the function that operates on ListOfElement. 11 00:01:07,549 --> 00:01:13,290 And that's almost certainly going to produce ListOfString as well. 12 00:01:13,290 --> 00:01:25,220 Let's do a purpose, produce list of the names of all the elements in the tree. 13 00:01:25,220 --> 00:01:32,812 We'll do a couple stubs, all-names--element which consumes e 14 00:01:32,812 --> 00:01:45,460 produces, empty and all-names--loe which consumes an loe procudes empty also. 15 00:01:45,460 --> 00:01:51,532 So those are the stubs running to be sure there were formed, they are, there's no 16 00:01:51,532 --> 00:01:58,590 test so they're not running so they're highlighted in black. 17 00:02:00,080 --> 00:02:05,980 Okay, let's do some examples. Check-expect all-names--, now which one 18 00:02:05,980 --> 00:02:13,558 should I test first? Let's go look at the type comment. 19 00:02:13,558 --> 00:02:19,900 Up here at the type comments, what we're looking for is what is the base case. 20 00:02:21,460 --> 00:02:25,850 Remember, the base case is a place where the reference cycles stop. 21 00:02:25,850 --> 00:02:29,942 It isn't here an element, because the only thing that happens in element is 22 00:02:29,942 --> 00:02:33,704 make-alt of these three fields, and ListOfElement is a reference to 23 00:02:33,704 --> 00:02:38,298 ListOfElement. So let's look in here for the base case, 24 00:02:38,298 --> 00:02:43,238 and here we see that the base case is operating on an empty ListOfElement. 25 00:02:43,238 --> 00:02:47,078 Because this isn't the base case, the cons case isn't the base case, that goes 26 00:02:47,078 --> 00:02:50,738 in a cycle of ListOfElement and it also goes back up to element, so an empty 27 00:02:50,738 --> 00:02:57,164 ListOfElement is the base case. So now we can go back down to where we're 28 00:02:57,164 --> 00:03:02,105 working and we know that to test the base case first we're going to start with 29 00:03:02,105 --> 00:03:07,528 all-names--loe of empty. What is all-names of an empty 30 00:03:07,528 --> 00:03:11,490 ListOfElements produced? Well, that sounds like empty. 31 00:03:11,490 --> 00:03:14,430 We're still not quite certain that this function is supposed to produce 32 00:03:14,430 --> 00:03:17,556 ListOfString. But assuming it is for now, it would 33 00:03:17,556 --> 00:03:21,620 clearly produce empty in this case. Let's do another case. 34 00:03:21,620 --> 00:03:25,725 We've done the base case but let's also try to do a simple case now. 35 00:03:25,725 --> 00:03:29,379 And what I want to do is go back up here and get this figure and copy it down 36 00:03:29,379 --> 00:03:33,513 here. It's really great that DrRacket lets you 37 00:03:33,513 --> 00:03:36,570 do this. You should enjoy it now, because not 38 00:03:36,570 --> 00:03:39,224 every programming environment will let you do it. 39 00:03:39,224 --> 00:03:47,694 So we've tested the empty ListOfElements case, let's now check all-names-element 40 00:03:47,694 --> 00:03:55,094 and let's check F1. Well, what are all the elements in the 41 00:03:55,094 --> 00:04:01,200 trees starting in F1. Well, it's just F1 because F1 has no sub 42 00:04:01,200 --> 00:04:09,200 elements. So all the names are list F1. 43 00:04:09,200 --> 00:04:15,102 Alright, let's check another case. Let's check all the names in D4 Well, 44 00:04:15,102 --> 00:04:24,070 what are all the elements in D4. Well, there's D4, F1, and F2. 45 00:04:24,070 --> 00:04:31,456 So, those are the names, D4, F1, and F2. Let's do another one. 46 00:04:31,456 --> 00:04:37,140 So we've done F1, there's no use doing F2 or F3 because they're the same as F1. 47 00:04:37,140 --> 00:04:41,083 And there's really no use doing D5, because D5 is simpler than D4. 48 00:04:42,330 --> 00:04:45,960 Instead maybe we shouldn't have done D5 first because it's simpler than D4, not 49 00:04:45,960 --> 00:04:49,590 much simpler but it's even little simpler so let's do it and we'll produce, what 50 00:04:49,590 --> 00:04:54,400 would it produce? Well it would produce D5 as the first 51 00:04:54,400 --> 00:05:03,037 thing and F3 as the second. And now what's D6 going to produce? 52 00:05:03,037 --> 00:05:12,303 Well let's see, D6. Well, D6 has D6 in it for sure and what 53 00:05:12,303 --> 00:05:18,941 else does it have in it? Well it has everything in D4. 54 00:05:22,810 --> 00:05:29,548 Is all of that, and everything in D5, which is all of that. 55 00:05:29,548 --> 00:05:36,563 And let's see, these two lists have to combined and that has to be put on the 56 00:05:36,563 --> 00:05:41,544 front. So one way of saying that is appending 57 00:05:41,544 --> 00:05:47,271 those two lists together, and causing that single item on the front. 58 00:05:47,271 --> 00:05:57,242 You could of course just write the value, you wouldn't have to write the 59 00:05:57,242 --> 00:06:05,271 elaboration. So you could just write, just write it 60 00:06:05,271 --> 00:06:09,905 this way. But the elaboration might be helpful 61 00:06:09,905 --> 00:06:15,270 especially for a case a little bit complicated like that. 62 00:06:15,270 --> 00:06:21,120 Okay, let's run it, all-names-element is not defined. 63 00:06:21,120 --> 00:06:25,120 Oh, I didn't follow my naming convention properly. 64 00:06:25,120 --> 00:06:28,353 And since I cut and pasted, I didn't follow my naming convention properly 65 00:06:28,353 --> 00:06:36,080 several times. Okay, the tests are all well formed. 66 00:06:36,080 --> 00:06:38,900 Let's Save this, it's always good to save often. 67 00:06:39,920 --> 00:06:43,430 Okay, so let's comment on the stubs and let's go get the templates and I'll show 68 00:06:43,430 --> 00:06:47,242 you a trick. If you go right here you'll get a list of 69 00:06:47,242 --> 00:06:51,866 every definition in the file. So as file start to get bigger and you 70 00:06:51,866 --> 00:06:55,831 can jump to individual definitions more quickly this way and all good program 71 00:06:55,831 --> 00:06:59,890 environments give you a feature like this. 72 00:06:59,890 --> 00:07:07,729 So, I'll go to fn-for-element, and I'll grab the two templates, and then we'll go 73 00:07:07,729 --> 00:07:16,500 back down where we were and I'll get rid of these comments. 74 00:07:16,500 --> 00:07:19,240 I'll do the renaming. Remember there's mutual recursion here, 75 00:07:19,240 --> 00:07:21,920 so I have to be careful to get all the references. 76 00:07:21,920 --> 00:07:26,795 There's that one and then there's this natural mutual recursion here and then 77 00:07:26,795 --> 00:07:31,520 when I rename the loe function there's the definition, there's the natural 78 00:07:31,520 --> 00:07:37,310 recursion and there's the natural mutual recursion. 79 00:07:37,310 --> 00:07:42,170 So I get all those. So now let's work off the examples. 80 00:07:42,170 --> 00:07:46,830 The first example tells me that if call all-names--loe with empty, I get empty. 81 00:07:51,980 --> 00:08:01,690 The second example tells me that if I call all-names--element of F1 I get F1. 82 00:08:01,690 --> 00:08:09,566 Let's see. In that particular case, this would be 83 00:08:09,566 --> 00:08:13,135 F1. And what would this natural mutual 84 00:08:13,135 --> 00:08:16,065 recursion be. Remember I'm reluctant to delete natural 85 00:08:16,065 --> 00:08:21,406 recursions or natural mutual recursions. [INAUDIBLE] would all be names--loe of 86 00:08:21,406 --> 00:08:25,852 empty because F1 has no sums and we already know that's going to produce 87 00:08:25,852 --> 00:08:31,612 empty. And that seems kind of natural. 88 00:08:31,612 --> 00:08:38,830 Seems natural to just cons F1 onto the natural recursion. 89 00:08:38,830 --> 00:08:43,575 That's also what this very complicated example was suggesting to us, was that 90 00:08:43,575 --> 00:08:48,300 you would cons the first thing onto the recursion. 91 00:08:48,300 --> 00:08:52,186 At this point it's really clear that this function, the one that consumes ListOf 92 00:08:52,186 --> 00:08:55,898 Element has to produce ListOfString set of question marks and I might even do 93 00:08:55,898 --> 00:09:01,150 this. You can get rid of this note. 94 00:09:01,150 --> 00:09:04,290 Let's see, I'm almost done. I just have this case. 95 00:09:04,290 --> 00:09:11,748 This is a case where all-names--loe is called with a ListOfElements that isn't 96 00:09:11,748 --> 00:09:16,160 empty. And we don't exactly have that case. 97 00:09:16,160 --> 00:09:24,720 Let's put that case in here. So let's say it's called with D4 and D5. 98 00:09:24,720 --> 00:09:39,605 Well, what's it supposed to produce? Well it's gotta produce everything in D4 99 00:09:39,605 --> 00:09:47,120 and everything in D5 combined into a single list. 100 00:09:47,120 --> 00:09:53,924 And again the way you combine two lists is with append, so that suggests that 101 00:09:53,924 --> 00:10:02,070 this should be append. Let's try running it. 102 00:10:02,070 --> 00:10:06,010 Check expect expects two arguments, but found only one. 103 00:10:07,220 --> 00:10:11,160 it's telling me that this is the whole check-expect so that's not right. 104 00:10:11,160 --> 00:10:14,747 I've got an extra parenthesis there. Whenever you have an extra parenthesis 105 00:10:14,747 --> 00:10:18,495 there you almost surely are missing one a little farther along. 106 00:10:18,495 --> 00:10:25,898 There, now let's try it. One of the tests failed. 107 00:10:25,898 --> 00:10:36,885 D4, F1, F2, so this produced, I'm just going to grab what it produced here. 108 00:10:36,885 --> 00:10:40,661 Actually, because I've got my screen small for recording, I have to be a 109 00:10:40,661 --> 00:10:44,740 little bit careful here. I'll slide this down here. 110 00:10:44,740 --> 00:10:49,010 I'll click here to see what test it is. I'll reselect this. 111 00:10:49,010 --> 00:10:55,618 So in this test, for D4 and D5, It produced, oh I have them in the wrong 112 00:10:55,618 --> 00:11:04,020 order. I just have my text examples in the wrong 113 00:11:04,020 --> 00:11:16,030 order because I asked D4 or D5, but over here I put the order 54. 114 00:11:16,030 --> 00:11:19,551 Let's Save it and run it, all twelve test passed. 115 00:11:19,551 --> 00:11:27,043 Let's look at the whole function again. We'll delete this figure. 116 00:11:27,043 --> 00:11:32,011 Again, this was almost entirely following the how to design functions recipe that 117 00:11:32,011 --> 00:11:38,374 we've come to understand quite well now. The only wrinkle that came in because of 118 00:11:38,374 --> 00:11:42,260 the mutually referential types was that we had to design two functions. 119 00:11:42,260 --> 00:11:45,590 We had to think a little bit harder about what was going to be the base case test. 120 00:11:45,590 --> 00:11:49,250 We used a naming convention to have two functions of different names that 121 00:11:49,250 --> 00:11:52,664 operated on the mutually referential types. 122 00:11:52,664 --> 00:11:57,169 That's really about it. This is mostly an ordinary how to design 123 00:11:57,169 --> 00:12:00,000 functions problem with more complicated data.