Now we're going to design functions operating arbitrary-arity trees.
And what we're going to see is that even though mutual reference and types is the
most complicated data we've so far the function design is pretty straight
forward. It falls out from what we already know.
Now that we've got complete data definitions for our mutually recursive
types, the data thats going to represent the file system structure for us.
Now we can start defining functions, and the thing thats going to be pretty cool
here is, designing these functions is actually going to go very smoothly and
easily, because of all the method we've learned so far.
Here we go. I'm in FS-V1, and in this version of the
file this is just the file we had last time except that I went ahead and added a
little picture of this directory structure, if that's going to make it
easier to design functions. If I had just been working by myself, I
would have scrolled that out on a napkin or something but I popped it in there for
you. and also, there's four function problems.
I'm not going to do all of them. In this video, I'll just do the first
one, and I'll do another one, and then the other ones you'll do on your own.
So here we go. We're going to design a function that
consumes element and produces the sum of all the file data in the tray.
So for example, in this tray, because the data is always the number for a file If
we sum this entire tree, well that data is zero because it has subs, that data's
zero. That data is one, that data is two, that
data is three. So 1 plus 2 plus 3 equals 6.
That's the function we're trying to write.
So let's go ahead and follow the method and do it.
Now, the key thing is when you design functions that operate on mutually
recursive types, and the data has mutual recursion in it.
We design multiple functions at once. So here, I know there's two types that
involve mutual recursion. I'm going to do two functions right away.
So I'm going to write element to. Let's see.
I'm adding up the data. And the data is always an integer so this
is going to be a sum of integers. So that's element to integer and also
list of element, because remember, I'm going to do both types to, well I don't
know what this is going to be. It might be integer because that's what
element produces. But it might be something else sometimes,
oftentimes it's the same. Both mutually recursive functions produce
the same type, but not always, so that's why I put those question marks there, to
remind me to come back and check that. Now I'm going to say, produce the sum of
all the data in element and its subs. I'm writing the purpose for the first
function. I'm writing the purpose for the function
that consumes element, because that's what I was asked to do.
Now, I'm going to do two stubs, and I'm going to call this function sumData.
Except there's not going to be one function, there's going to be two.
Right there's going to be the one that consumes element and the one that
consumes list development. So the naming convention I'm going to use
is like this. I'm going to say some data dash dash
element. That's the one that operates on element,
the stub for that is zero. And some data dash dash, list of element,
consumes list of element. And the stub for that is probably zero,
we'll come back to that. Now let's do some check expects.
Check expect sum data dash dash element. Now, there's recursion involved, so we
should start with the base case. It's example and when you've got mutual
reference it's not clear quite what is the base case example.
There tends to be more than one but one example is sum data, dash, dash, element
of F1. That's just, know what I'm going to do?
I'm going to go up here and get this figure, and bring it down here
temporarily. I'll just bring a copy of it right here
so we can refer to it as we work, and then we'll just delete it later and we're
done. Some data, element of f1, f1 is a file
for which the data is 1, so that produces 1...
That seems like at least a close to base case example because F1 has no sums, so
there's no recursion there. Another base case example might be one
that we don't quite have in here, but sum-data list of element of empty.
What's the sum of all the data in an empty list of elements?
Well that's zero. Now let's try to do the next simplest
example I can think of, which is sum data dash, dash dash element of D5.
That's pretty simple cause D5 only has one sub.
Well, the sum of all the data in d5. Remember, things that have subs don't
have data. So the actual value there is zero.
So that's just three, and let's do sum data of d4.
Well that's also 3 because 1 plus 2 is 3. That's plus 1 and 2.
Now let's do the top one too. Sum-data of D6 is, what is it, well, it's
1 plus 2 plus 3. And now it's really starting to look like
sum-data LOE has gotta produce an integer, because there's sort of this
meaningful notion of what's the sum of all the data in an empty list of
elements. So this is really starting to look like
it's going to be integer, but let's keep going.
Okay, signature, purpose, stub, examples, let's go get the templates.
Here's the templates. I also commented them out so that they
wouldn't get highlighted in black when we run the program.
There they are. Now we'll comment out the stubs.
We'll uncomment the templates, and when you got mutual recursion, you really need
to be careful about the renaming of the templates.
So fn for element is going to be called sun-data element, and there's a mutually
recursive call down here that I need to be sure to rename as well.
And fun for LOE is going to be called sum data dash dash LOE.
And there it is. And there's it's recursive, it's natural
recursion, but, here's the natural mutual recursion.
So you need to be sure to name the mutual recursions as well as the function
definitions and the self recursions. Okay, let's see.
I want to sum the data in an element. And interpretation, remember the
interpretation is that if data is zero then subs is considered to be a list of
sub-elements and if data is not zero then subs is ignored.
So to know how to interpret a given element, you need to look at data first,
you need to know is data zero. Let's start by doing that.
It doesn't look like name has anything to do in this function, so I'll just get rid
of it. And I'll start with If zero, is the data,
zero. Now, if the data's zero, it means I'm
supposed to go look in the subs to see how much data is there.
So, I'll leave the natural mutual recursion to do its work.
If the data is not zero then, then this, this element is a file.
It has data. So we're going to produce the size of
this data. Now let's look at some data LOE.
Well the sum of an empty list of elements, intuition plus this example
here, tells me is zero. And otherwise, you know when you've got
mutual recursion. You've got in a big way trust the natural
recursions. You've got to trust the natural
self-recursion. You've got to trust the natural mutual
recursion. If I've got a list of elements, and I
have the first element in my hand and the rest of the elements in my hand, what's
the sum of all the data in them? Well, it's the sum of the data in the
first plus the data in the rest. This just becomes a plus.
As I'm trusting that this thing is going to do what it said it would do.
And this thing is going to do what it said it would do, and now it's really
clear here, now that I have this plus and also I'm returning some data LOE here.
This really is integer. We're counting on the list development
function to produce the same type of result as the element function.
As I said, when you have mutually recursive functions, it's usually the
case that all of the functions produce the same type of data.
But there's some exceptions to that rule. So there we go.
We filled in all the dots. What happens?
So let me save it and try running it. All five tests passed.
Now, you may have a little feeling there like you had the first time you wrote a
recursive function. Why did that work?
The reason it worked is we had these well formed self referential type comments, it
was always a base case and that means we got templates derived from that.
That supported natural mutual recursions in the right place and that have a base
case. Right here.
We formed our examples carefully and systematically encoded to them and we get
a mutual recursion that has the right structure.
And that always terminates in a base case.
So again, what you're seeing here, is, that, the way the method works by being
data driven. In terms of getting well formed self and
mutually referential type comments to the templates.
Coding those to complete the functions, trusting the natural recursions, that
makes functions like this quite easy to design.
What I'd like you to do now is do this next problem, where you design a function
that consumes element, and produces a list of all of the elements in the tree.
So that was pretty straightforward. The key point really is that when you
design functions operating on mutually referential types, you don't design a
single function, you design one for each type.
And so it pays to group the signatures together to maybe right a single purpose
to group the examples and then group the functions.
That makes it easier to work on them. Another issue has to do with the
examples. These are mutually recursive functions so
you want base case first but sometimes it's a bit more natural to put a case one
away from the base case first as it was in this case.
It's worth noting here that the method we're presenting in this course is really
starting to pay off here. In a lot of other approaches, functions
that operate on trees would be very different from functions that operate on
lists. It wouldn't be the natural extension it
was here. Really the only thing we learned in the
latter part of this week, was mutual reference in type comments.
After that, we really knew how to complete those data definitions, and
write those functions. I think that's pretty cool.