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.