1 00:00:00,025 --> 00:00:08,810 Now we're going to design functions operating arbitrary-arity trees. 2 00:00:10,720 --> 00:00:14,624 And what we're going to see is that even though mutual reference and types is the 3 00:00:14,624 --> 00:00:18,406 most complicated data we've so far the function design is pretty straight 4 00:00:18,406 --> 00:00:22,800 forward. It falls out from what we already know. 5 00:00:22,800 --> 00:00:26,826 Now that we've got complete data definitions for our mutually recursive 6 00:00:26,826 --> 00:00:32,469 types, the data thats going to represent the file system structure for us. 7 00:00:32,469 --> 00:00:36,693 Now we can start defining functions, and the thing thats going to be pretty cool 8 00:00:36,693 --> 00:00:40,789 here is, designing these functions is actually going to go very smoothly and 9 00:00:40,789 --> 00:00:46,310 easily, because of all the method we've learned so far. 10 00:00:46,310 --> 00:00:49,278 Here we go. I'm in FS-V1, and in this version of the 11 00:00:49,278 --> 00:00:53,625 file this is just the file we had last time except that I went ahead and added a 12 00:00:53,625 --> 00:00:57,558 little picture of this directory structure, if that's going to make it 13 00:00:57,558 --> 00:01:03,741 easier to design functions. If I had just been working by myself, I 14 00:01:03,741 --> 00:01:07,107 would have scrolled that out on a napkin or something but I popped it in there for 15 00:01:07,107 --> 00:01:11,641 you. and also, there's four function problems. 16 00:01:11,641 --> 00:01:15,085 I'm not going to do all of them. In this video, I'll just do the first 17 00:01:15,085 --> 00:01:19,705 one, and I'll do another one, and then the other ones you'll do on your own. 18 00:01:19,705 --> 00:01:22,939 So here we go. We're going to design a function that 19 00:01:22,939 --> 00:01:27,697 consumes element and produces the sum of all the file data in the tray. 20 00:01:27,697 --> 00:01:32,247 So for example, in this tray, because the data is always the number for a file If 21 00:01:32,247 --> 00:01:36,797 we sum this entire tree, well that data is zero because it has subs, that data's 22 00:01:36,797 --> 00:01:42,855 zero. That data is one, that data is two, that 23 00:01:42,855 --> 00:01:47,440 data is three. So 1 plus 2 plus 3 equals 6. 24 00:01:47,440 --> 00:01:49,820 That's the function we're trying to write. 25 00:01:49,820 --> 00:01:51,640 So let's go ahead and follow the method and do it. 26 00:01:54,180 --> 00:01:57,840 Now, the key thing is when you design functions that operate on mutually 27 00:01:57,840 --> 00:02:02,130 recursive types, and the data has mutual recursion in it. 28 00:02:02,130 --> 00:02:06,422 We design multiple functions at once. So here, I know there's two types that 29 00:02:06,422 --> 00:02:10,510 involve mutual recursion. I'm going to do two functions right away. 30 00:02:10,510 --> 00:02:12,960 So I'm going to write element to. Let's see. 31 00:02:12,960 --> 00:02:20,952 I'm adding up the data. And the data is always an integer so this 32 00:02:20,952 --> 00:02:26,731 is going to be a sum of integers. So that's element to integer and also 33 00:02:26,731 --> 00:02:31,133 list of element, because remember, I'm going to do both types to, well I don't 34 00:02:31,133 --> 00:02:37,342 know what this is going to be. It might be integer because that's what 35 00:02:37,342 --> 00:02:41,890 element produces. But it might be something else sometimes, 36 00:02:41,890 --> 00:02:46,509 oftentimes it's the same. Both mutually recursive functions produce 37 00:02:46,509 --> 00:02:50,931 the same type, but not always, so that's why I put those question marks there, to 38 00:02:50,931 --> 00:02:59,010 remind me to come back and check that. Now I'm going to say, produce the sum of 39 00:02:59,010 --> 00:03:07,218 all the data in element and its subs. I'm writing the purpose for the first 40 00:03:07,218 --> 00:03:09,662 function. I'm writing the purpose for the function 41 00:03:09,662 --> 00:03:12,953 that consumes element, because that's what I was asked to do. 42 00:03:12,953 --> 00:03:20,570 Now, I'm going to do two stubs, and I'm going to call this function sumData. 43 00:03:20,570 --> 00:03:23,524 Except there's not going to be one function, there's going to be two. 44 00:03:23,524 --> 00:03:25,918 Right there's going to be the one that consumes element and the one that 45 00:03:25,918 --> 00:03:29,870 consumes list development. So the naming convention I'm going to use 46 00:03:29,870 --> 00:03:32,741 is like this. I'm going to say some data dash dash 47 00:03:32,741 --> 00:03:35,567 element. That's the one that operates on element, 48 00:03:35,567 --> 00:03:41,838 the stub for that is zero. And some data dash dash, list of element, 49 00:03:41,838 --> 00:03:47,936 consumes list of element. And the stub for that is probably zero, 50 00:03:47,936 --> 00:03:55,323 we'll come back to that. Now let's do some check expects. 51 00:03:55,323 --> 00:04:03,539 Check expect sum data dash dash element. Now, there's recursion involved, so we 52 00:04:03,539 --> 00:04:08,720 should start with the base case. It's example and when you've got mutual 53 00:04:08,720 --> 00:04:13,548 reference it's not clear quite what is the base case example. 54 00:04:13,548 --> 00:04:17,643 There tends to be more than one but one example is sum data, dash, dash, element 55 00:04:17,643 --> 00:04:21,599 of F1. That's just, know what I'm going to do? 56 00:04:21,599 --> 00:04:25,322 I'm going to go up here and get this figure, and bring it down here 57 00:04:25,322 --> 00:04:28,902 temporarily. I'll just bring a copy of it right here 58 00:04:28,902 --> 00:04:32,126 so we can refer to it as we work, and then we'll just delete it later and we're 59 00:04:32,126 --> 00:04:36,620 done. Some data, element of f1, f1 is a file 60 00:04:36,620 --> 00:04:41,815 for which the data is 1, so that produces 1... 61 00:04:41,815 --> 00:04:45,975 That seems like at least a close to base case example because F1 has no sums, so 62 00:04:45,975 --> 00:04:56,222 there's no recursion there. Another base case example might be one 63 00:04:56,222 --> 00:05:04,450 that we don't quite have in here, but sum-data list of element of empty. 64 00:05:04,450 --> 00:05:06,990 What's the sum of all the data in an empty list of elements? 65 00:05:06,990 --> 00:05:12,190 Well that's zero. Now let's try to do the next simplest 66 00:05:12,190 --> 00:05:24,360 example I can think of, which is sum data dash, dash dash element of D5. 67 00:05:24,360 --> 00:05:27,710 That's pretty simple cause D5 only has one sub. 68 00:05:27,710 --> 00:05:32,896 Well, the sum of all the data in d5. Remember, things that have subs don't 69 00:05:32,896 --> 00:05:36,165 have data. So the actual value there is zero. 70 00:05:36,165 --> 00:05:44,474 So that's just three, and let's do sum data of d4. 71 00:05:46,570 --> 00:05:51,480 Well that's also 3 because 1 plus 2 is 3. That's plus 1 and 2. 72 00:05:51,480 --> 00:05:59,171 Now let's do the top one too. Sum-data of D6 is, what is it, well, it's 73 00:05:59,171 --> 00:06:05,952 1 plus 2 plus 3. And now it's really starting to look like 74 00:06:05,952 --> 00:06:09,432 sum-data LOE has gotta produce an integer, because there's sort of this 75 00:06:09,432 --> 00:06:12,738 meaningful notion of what's the sum of all the data in an empty list of 76 00:06:12,738 --> 00:06:17,154 elements. So this is really starting to look like 77 00:06:17,154 --> 00:06:20,320 it's going to be integer, but let's keep going. 78 00:06:20,320 --> 00:06:23,778 Okay, signature, purpose, stub, examples, let's go get the templates. 79 00:06:23,778 --> 00:06:28,607 Here's the templates. I also commented them out so that they 80 00:06:28,607 --> 00:06:32,465 wouldn't get highlighted in black when we run the program. 81 00:06:32,465 --> 00:06:40,235 There they are. Now we'll comment out the stubs. 82 00:06:40,235 --> 00:06:46,652 We'll uncomment the templates, and when you got mutual recursion, you really need 83 00:06:46,652 --> 00:06:52,598 to be careful about the renaming of the templates. 84 00:06:52,598 --> 00:06:56,502 So fn for element is going to be called sun-data element, and there's a mutually 85 00:06:56,502 --> 00:07:01,400 recursive call down here that I need to be sure to rename as well. 86 00:07:04,130 --> 00:07:07,665 And fun for LOE is going to be called sum data dash dash LOE. 87 00:07:07,665 --> 00:07:11,775 And there it is. And there's it's recursive, it's natural 88 00:07:11,775 --> 00:07:16,940 recursion, but, here's the natural mutual recursion. 89 00:07:16,940 --> 00:07:21,820 So you need to be sure to name the mutual recursions as well as the function 90 00:07:21,820 --> 00:07:27,040 definitions and the self recursions. Okay, let's see. 91 00:07:27,040 --> 00:07:33,952 I want to sum the data in an element. And interpretation, remember the 92 00:07:33,952 --> 00:07:38,236 interpretation is that if data is zero then subs is considered to be a list of 93 00:07:38,236 --> 00:07:44,110 sub-elements and if data is not zero then subs is ignored. 94 00:07:44,110 --> 00:07:48,807 So to know how to interpret a given element, you need to look at data first, 95 00:07:48,807 --> 00:07:54,484 you need to know is data zero. Let's start by doing that. 96 00:07:54,484 --> 00:07:59,509 It doesn't look like name has anything to do in this function, so I'll just get rid 97 00:07:59,509 --> 00:08:04,161 of it. And I'll start with If zero, is the data, 98 00:08:04,161 --> 00:08:08,016 zero. Now, if the data's zero, it means I'm 99 00:08:08,016 --> 00:08:14,190 supposed to go look in the subs to see how much data is there. 100 00:08:14,190 --> 00:08:17,119 So, I'll leave the natural mutual recursion to do its work. 101 00:08:18,260 --> 00:08:22,910 If the data is not zero then, then this, this element is a file. 102 00:08:22,910 --> 00:08:25,978 It has data. So we're going to produce the size of 103 00:08:25,978 --> 00:08:31,630 this data. Now let's look at some data LOE. 104 00:08:31,630 --> 00:08:36,386 Well the sum of an empty list of elements, intuition plus this example 105 00:08:36,386 --> 00:08:42,815 here, tells me is zero. And otherwise, you know when you've got 106 00:08:42,815 --> 00:08:48,566 mutual recursion. You've got in a big way trust the natural 107 00:08:48,566 --> 00:08:51,218 recursions. You've got to trust the natural 108 00:08:51,218 --> 00:08:54,310 self-recursion. You've got to trust the natural mutual 109 00:08:54,310 --> 00:08:57,667 recursion. If I've got a list of elements, and I 110 00:08:57,667 --> 00:09:02,412 have the first element in my hand and the rest of the elements in my hand, what's 111 00:09:02,412 --> 00:09:10,843 the sum of all the data in them? Well, it's the sum of the data in the 112 00:09:10,843 --> 00:09:16,810 first plus the data in the rest. This just becomes a plus. 113 00:09:16,810 --> 00:09:24,970 As I'm trusting that this thing is going to do what it said it would do. 114 00:09:26,030 --> 00:09:29,393 And this thing is going to do what it said it would do, and now it's really 115 00:09:29,393 --> 00:09:35,090 clear here, now that I have this plus and also I'm returning some data LOE here. 116 00:09:35,090 --> 00:09:39,164 This really is integer. We're counting on the list development 117 00:09:39,164 --> 00:09:44,980 function to produce the same type of result as the element function. 118 00:09:44,980 --> 00:09:48,160 As I said, when you have mutually recursive functions, it's usually the 119 00:09:48,160 --> 00:09:52,130 case that all of the functions produce the same type of data. 120 00:09:52,130 --> 00:09:55,192 But there's some exceptions to that rule. So there we go. 121 00:09:55,192 --> 00:10:00,040 We filled in all the dots. What happens? 122 00:10:00,040 --> 00:10:04,319 So let me save it and try running it. All five tests passed. 123 00:10:04,319 --> 00:10:11,935 Now, you may have a little feeling there like you had the first time you wrote a 124 00:10:11,935 --> 00:10:21,360 recursive function. Why did that work? 125 00:10:21,360 --> 00:10:25,983 The reason it worked is we had these well formed self referential type comments, it 126 00:10:25,983 --> 00:10:32,400 was always a base case and that means we got templates derived from that. 127 00:10:32,400 --> 00:10:36,755 That supported natural mutual recursions in the right place and that have a base 128 00:10:36,755 --> 00:10:39,017 case. Right here. 129 00:10:39,017 --> 00:10:44,693 We formed our examples carefully and systematically encoded to them and we get 130 00:10:44,693 --> 00:10:50,001 a mutual recursion that has the right structure. 131 00:10:50,001 --> 00:10:53,919 And that always terminates in a base case. 132 00:10:53,919 --> 00:10:58,207 So again, what you're seeing here, is, that, the way the method works by being 133 00:10:58,207 --> 00:11:02,245 data driven. In terms of getting well formed self and 134 00:11:02,245 --> 00:11:06,233 mutually referential type comments to the templates. 135 00:11:07,480 --> 00:11:12,304 Coding those to complete the functions, trusting the natural recursions, that 136 00:11:12,304 --> 00:11:16,500 makes functions like this quite easy to design. 137 00:11:16,500 --> 00:11:20,340 What I'd like you to do now is do this next problem, where you design a function 138 00:11:20,340 --> 00:11:26,060 that consumes element, and produces a list of all of the elements in the tree. 139 00:11:26,060 --> 00:11:32,430 So that was pretty straightforward. The key point really is that when you 140 00:11:32,430 --> 00:11:36,192 design functions operating on mutually referential types, you don't design a 141 00:11:36,192 --> 00:11:39,980 single function, you design one for each type. 142 00:11:41,080 --> 00:11:44,850 And so it pays to group the signatures together to maybe right a single purpose 143 00:11:44,850 --> 00:11:49,400 to group the examples and then group the functions. 144 00:11:49,400 --> 00:11:53,636 That makes it easier to work on them. Another issue has to do with the 145 00:11:53,636 --> 00:11:58,048 examples. These are mutually recursive functions so 146 00:11:58,048 --> 00:12:02,400 you want base case first but sometimes it's a bit more natural to put a case one 147 00:12:02,400 --> 00:12:07,730 away from the base case first as it was in this case. 148 00:12:07,730 --> 00:12:11,683 It's worth noting here that the method we're presenting in this course is really 149 00:12:11,683 --> 00:12:16,684 starting to pay off here. In a lot of other approaches, functions 150 00:12:16,684 --> 00:12:19,756 that operate on trees would be very different from functions that operate on 151 00:12:19,756 --> 00:12:23,750 lists. It wouldn't be the natural extension it 152 00:12:23,750 --> 00:12:27,498 was here. Really the only thing we learned in the 153 00:12:27,498 --> 00:12:32,360 latter part of this week, was mutual reference in type comments. 154 00:12:32,360 --> 00:12:36,077 After that, we really knew how to complete those data definitions, and 155 00:12:36,077 --> 00:12:40,350 write those functions. I think that's pretty cool.