In the last video, you saw the type comments for an arbitrary arity tree, and
you saw how the mutual reference works in those type comments.
Because of the two cycles, the tree can be arbitrary wide at any point, and it
can also be arbitrarily deep. You have now seen the most important part
about arbitrary arity trees. In this video, we're going to do the
templates, and there won't be any new template rules.
The templates are just going to fall out from what we already know.
So, now I'm back in fs starter.racket. And again, we've got the two types which
have mutual recursion, and we're going to do the templates.
And the interesting thing we're going to see about the templates is, we already
know how to do them. Just a reminder, when we have types that
involve mutual recursion, what I do is put each type and interpretation
together. So, there's element and its
interpretation, list of element and its interpretation.
Then I put all the examples, and now I'm going to put all of the templates
together. And that's going to be much easier for us
when we go to design the functions, and it also helps us see the mutual reference
structure better. So, here we go, there's going to be two
templates, because there's two mutually recursive types.
So, there's going to be that template and that template.
And let's see, notice I'm not putting the template rules used, because you're not
required to do that anymore, but I'll talk about them as we do it.
This is a compound data, so, there's all three selectors.
And then I'm going to decorate that with the types of the value that comes back
from the selector. So, in the case of main, it's a string.
In the case of data, it's an integer. And in the case of subs, it's a
ListOfElement. Now, ListOfElement is a non-primitive
type, it's a type that we define. So, the reference rule here says that we
should wrap this selector into a call for fn-for-loe loe.
And I'm going to go ahead and do that, like that.
Now, we're done with fun for element. For fun for loe, well, let's see, this is
one of the two cases. So, there's a con with the two cases,
first case is [UNKNOWN] distinct empty. Second case is the second case so, we'll
say else, then it's a compound cons, first loe, rest loe, second we'll just
decorate those. Well, this is an element, and this is a
ListOfElement. Reference here says that we'll wrap this
in fn-for-element, and the self reference rule here says we'll go fn-for-loe.
So, there we go, we've go the template for both types.
And we didn't really need a new template rule.
The reference rule and the self reference rule, just work to produce the right
answer. In some sense, the only new rule for
templating types involving mutual reference, is to do both templates at the
same time. That'll help you see the mutual recursion
structure in the templates corresponding to the mutual reference structure in the
types. And just to draw that out for you, let me
switch again to this kind of figure that we've seen before, where I've got both
the type comments and the templates. And you could see where there's a self
reference, there's a natural recursion, where there's a mutual reference cycle,
there is a natural mutual recursion. So fn-for-loe calls fn-for-element, and
fn-for-element calls fn-for-loe. In the next video, we'll see how that
plays out as we're designing the functions.