In this video, I'm going to design another function operating on element.
Remember that Element and ListOfElement are mutually referential types.
And so that means designing one function is actually going to end up designing two
of them. I mean, fs2-v2.racket and if I scroll
down here to the problem, here it is. Design a function that consumes element
and produces a list of the names of all the elements in the tree.
So I know right away consumes element and I need to know what list of names means,
so I go back up to the element data definition, and let's see for an element
the name is a string. So this is going to produce ListOfString
and of course there'll be the function that operates on ListOfElement.
And that's almost certainly going to produce ListOfString as well.
Let's do a purpose, produce list of the names of all the elements in the tree.
We'll do a couple stubs, all-names--element which consumes e
produces, empty and all-names--loe which consumes an loe procudes empty also.
So those are the stubs running to be sure there were formed, they are, there's no
test so they're not running so they're highlighted in black.
Okay, let's do some examples. Check-expect all-names--, now which one
should I test first? Let's go look at the type comment.
Up here at the type comments, what we're looking for is what is the base case.
Remember, the base case is a place where the reference cycles stop.
It isn't here an element, because the only thing that happens in element is
make-alt of these three fields, and ListOfElement is a reference to
ListOfElement. So let's look in here for the base case,
and here we see that the base case is operating on an empty ListOfElement.
Because this isn't the base case, the cons case isn't the base case, that goes
in a cycle of ListOfElement and it also goes back up to element, so an empty
ListOfElement is the base case. So now we can go back down to where we're
working and we know that to test the base case first we're going to start with
all-names--loe of empty. What is all-names of an empty
ListOfElements produced? Well, that sounds like empty.
We're still not quite certain that this function is supposed to produce
ListOfString. But assuming it is for now, it would
clearly produce empty in this case. Let's do another case.
We've done the base case but let's also try to do a simple case now.
And what I want to do is go back up here and get this figure and copy it down
here. It's really great that DrRacket lets you
do this. You should enjoy it now, because not
every programming environment will let you do it.
So we've tested the empty ListOfElements case, let's now check all-names-element
and let's check F1. Well, what are all the elements in the
trees starting in F1. Well, it's just F1 because F1 has no sub
elements. So all the names are list F1.
Alright, let's check another case. Let's check all the names in D4 Well,
what are all the elements in D4. Well, there's D4, F1, and F2.
So, those are the names, D4, F1, and F2. Let's do another one.
So we've done F1, there's no use doing F2 or F3 because they're the same as F1.
And there's really no use doing D5, because D5 is simpler than D4.
Instead maybe we shouldn't have done D5 first because it's simpler than D4, not
much simpler but it's even little simpler so let's do it and we'll produce, what
would it produce? Well it would produce D5 as the first
thing and F3 as the second. And now what's D6 going to produce?
Well let's see, D6. Well, D6 has D6 in it for sure and what
else does it have in it? Well it has everything in D4.
Is all of that, and everything in D5, which is all of that.
And let's see, these two lists have to combined and that has to be put on the
front. So one way of saying that is appending
those two lists together, and causing that single item on the front.
You could of course just write the value, you wouldn't have to write the
elaboration. So you could just write, just write it
this way. But the elaboration might be helpful
especially for a case a little bit complicated like that.
Okay, let's run it, all-names-element is not defined.
Oh, I didn't follow my naming convention properly.
And since I cut and pasted, I didn't follow my naming convention properly
several times. Okay, the tests are all well formed.
Let's Save this, it's always good to save often.
Okay, so let's comment on the stubs and let's go get the templates and I'll show
you a trick. If you go right here you'll get a list of
every definition in the file. So as file start to get bigger and you
can jump to individual definitions more quickly this way and all good program
environments give you a feature like this.
So, I'll go to fn-for-element, and I'll grab the two templates, and then we'll go
back down where we were and I'll get rid of these comments.
I'll do the renaming. Remember there's mutual recursion here,
so I have to be careful to get all the references.
There's that one and then there's this natural mutual recursion here and then
when I rename the loe function there's the definition, there's the natural
recursion and there's the natural mutual recursion.
So I get all those. So now let's work off the examples.
The first example tells me that if call all-names--loe with empty, I get empty.
The second example tells me that if I call all-names--element of F1 I get F1.
Let's see. In that particular case, this would be
F1. And what would this natural mutual
recursion be. Remember I'm reluctant to delete natural
recursions or natural mutual recursions. [INAUDIBLE] would all be names--loe of
empty because F1 has no sums and we already know that's going to produce
empty. And that seems kind of natural.
Seems natural to just cons F1 onto the natural recursion.
That's also what this very complicated example was suggesting to us, was that
you would cons the first thing onto the recursion.
At this point it's really clear that this function, the one that consumes ListOf
Element has to produce ListOfString set of question marks and I might even do
this. You can get rid of this note.
Let's see, I'm almost done. I just have this case.
This is a case where all-names--loe is called with a ListOfElements that isn't
empty. And we don't exactly have that case.
Let's put that case in here. So let's say it's called with D4 and D5.
Well, what's it supposed to produce? Well it's gotta produce everything in D4
and everything in D5 combined into a single list.
And again the way you combine two lists is with append, so that suggests that
this should be append. Let's try running it.
Check expect expects two arguments, but found only one.
it's telling me that this is the whole check-expect so that's not right.
I've got an extra parenthesis there. Whenever you have an extra parenthesis
there you almost surely are missing one a little farther along.
There, now let's try it. One of the tests failed.
D4, F1, F2, so this produced, I'm just going to grab what it produced here.
Actually, because I've got my screen small for recording, I have to be a
little bit careful here. I'll slide this down here.
I'll click here to see what test it is. I'll reselect this.
So in this test, for D4 and D5, It produced, oh I have them in the wrong
order. I just have my text examples in the wrong
order because I asked D4 or D5, but over here I put the order 54.
Let's Save it and run it, all twelve test passed.
Let's look at the whole function again. We'll delete this figure.
Again, this was almost entirely following the how to design functions recipe that
we've come to understand quite well now. The only wrinkle that came in because of
the mutually referential types was that we had to design two functions.
We had to think a little bit harder about what was going to be the base case test.
We used a naming convention to have two functions of different names that
operated on the mutually referential types.
That's really about it. This is mostly an ordinary how to design
functions problem with more complicated data.