So the last two videos, we saw some pretty amazing stuff.
We had a type comment that referred to itself, and then we have function that
called itself. And that function actually did what we
wanted it to do. Instead of just going around and around
in circles, on and on and on forever. Now, why is that?
That's what I'm going to talk about in this video.
There's some pretty deep computer science underlying all of this.
And we're not going to get into it, in, in kind of, more academic terms.
But what we will see is that the type comment has two key properties.
And the way we derive the template preserves those properties.
So that we end up with functions that work properly, even though they call
themselves. So what I'm going to do is explain that.,
make a few additions to the design recipes.
So that you can keeping doing that systematically and producing recursive
functions that work properly on your own. This file is quidditch recap starter.
It's basically just the solutions from the last video rearranged slightly so so
that I had both parts of the problem in one box.
That gives me some room below. The first thing I want to know is right
here in the Problem description. Notice that we're designing a program
that will keep track of your favorite quidditch teams.
Now, ask yourself, how many teams are there?
We don't know ahead of time. It could be one, it could be two, there
could be three, there could be 60, we just don't know ahead of time.
This is what we call, arbitrary sized. Arbitrary doesn't means random, it just
means we don't know ahead of time. Time now whenever we have an arbitrary
size data problem whenever we need data to be of arbitrary size.
What we're going to see is that we want to use self reference in the type
comment. This type comment has the self reference
in it as we noted before. And we saw how that made it possible for
it to account for lists of any size. We just make one more cycle around the
self-reference relationship for each element of the list.
But why does this self-reference work out?
Why doesn't it in some sense blow up? Because it just keeps going around.
Well, the key thing is that this is called a well formed self referential
data definition. And it's well formed because it has the
self reference case, that's true, that's what lets it get longer and longer.
But it also has the non self referential case, or the base case.
And that's what lets it stop. So in a well formed self referential data
definition, you always have both the base case that has no self reference, and a
self reference case. Now, this is a simple self referential
data definition. It's possible for these type comments to
have more than one self reference case, and more than one base case.
The rule for being well formed is that there has to be at least one base case,
non self referential case. And at least one self referential case.
So the summary so far is, if you have an arbitrary amount of information you need
to represent. You need to use a well formed self
referential data definition, that gets us to here.
And if we look at the how to design data page what we've got so far is reflected
here. And the choice of what form of data
definition to use. When information to be represented is of
arbitrary size, we use a self-referential data definition.
Neutrally referencial is something we'll talk about in another week.
So if we follow this link, it says that we need to use, for our arbitrary size
information. We need to use a well formed
self-referential data definitioning/g. So that's how the how to design data
recipe accounts for what we've seen in the code so far.
Let's go back to the code now, and let's talk quickly about the examples for
self-referential data definitions, it's good to have examples of the base case.
If there's more than one base case, then have examples of both base cases.
They tend to be kind of trivial, but I like to put them in anyways.
And you should have examples of the self-referential case.
In this particular data definition, I probably could have done with just two
examples rather than three. So I probably could have done with
example one and example three. It's fine to have an additional one.
Now, let me scroll a little bit and talk about the template.
As we saw before at the beginning of the templates relatively straightforward.
It's one of, with two cases, so that got us the cond.
The first case is atomic distinct empty, so that got us cond empty questionmark
los and dot dot dot. This case, the second case, is cond, so
that's compound. We take the cons apart into it's first
and it's rest. But then the question is how do we get
this fn-for-los? Well the reason we got that fn-for-los,
let me just back up a little bit to where we were right at that point in time.
We know that first los was going to be a string.
And we knew that rest los was ListOfString so we're not going to do
anything with first los because its primitive type string is a primitive
type. But with rest los here's where we're
getting the self reference this is self reference here back to listed string.
Well we take the rest of los, we're holding a value of type listed string.
And so there's a special template rule called the self reference rule.
And we use it in this case. And the self reference rule says, wrap
that selector in a call to the template function itself.
In this thing is what's called natural recursion.
It's a recursion that shows up, exactly where in the type comment we have a self
reference. So, what we have so far, is arbitrary
size data, well formed self-referential data definition.
Have examples of, the base case and self-reference case and in the template,
when you hit the self-reference, put in a natural recursion.
That last bit shows up in the data driven templates page.
Right here where it says, if you have a self reference, form a natural recursion
with a call to this type's template function, and that's what we did here.
We put a call to this type's template function, because we had a self reference
there. And that's why this call, this natural
recursion corresponds exactly to this self-reference.
And I've tried to draw the arrows here to show that correspondence clearly.
So from now on, whenever you see a self-reference in a type comment, you'll
immediately know that there's going to be a natural recursion in the template.
Now let's look at the function we designed.
So the signature is pretty straightforward.
Nothing really new here, except that it does consume ListOfString.
The purpose, similarly, we knew how to do, and the stub, and the check-expects
look pretty familiar. But there are a couple things I want to
note here about check-expects for functions operating on lists.
First, remember that check-expects are always examples first and tests later.
So, we use them as examples to help us figure out what we're doing.
And with that in mind, it's always a good idea to have the base case example first,
the base case test first. That's what I have here.
I have contains-ubc at empty as my first test.
Partly, that helps us figure out the simplest case first.
And also, many tests of these functions end up at the base case, and so if the
base case result is wrong, that can affect other tests.
So it's good to get the base case debugged first.
So there's two reasons to put the base case first, one it helps us figure out
the simplest thing first and the other it makes sure when we run the test.
That the base case works properly before we cast the other cases.
And another general guideline for functions operating on lists is to be
sure that you have a test that operates on a list thats at least two elements
long. That's because sometimes there's certain
kinds of bugs you can introduce that don't show up in one element lists.
This particular example is also an example of a function that has two
difference cases in it. There's cases where it finds the string
it's looking for and cases where it doesn't.
And so, in that case, you have to be able to test the true and false case.
Finally, let's look at the function itself and to look at the function.
What I want to do is I'm going to back up.
So what I'm going to do is I'm going to Delete this and go back to the point
where we just had the template. When you Copy the template down, for a
template based on our type with self reference.
The new template has a natural recursion in it and its very important when you
rename the function.. That you rename both the function
definition and any natural recursions. That's very important, and we'll see why
in a minute. So now, let me start coding the details.
Let's see if the function is operating on a list that's empty.
Then we can't find UBC in an empty list, so that would be false.
Otherwise, these examples tell me that there's two different cases depending on
the first item in the list. The first item is UBC, we produce true,
if it's not, we produce false. So that makes me put an if in here, and I
say string equal? UBC, if the first item in the list is
UBC, we're going to produce true. In otherwise, what do we need to do?
Well, first thing on the list, might not be the UBC but there might be, UBC
further down the list. So, we need to go look further down on
the list and the key point here is, that we want you to get you to trust the
natural recursion. At this point in time, you need to know
is UBC in the rest of the list. And because the template has included a
natural recursion. And because that natural recursion came
from a type with well formed self-reference, you can count on the
natural recursion to work. So we're just going to trust that
contains-ubc of rest los does what we need it to do.
The key thing is I want you to avoid the temptation to edit in here.
Trust the natural recursion, that's the game.
And the reason you can trust it is because it came from a well formed self
referencial type. Let's see, all four attempts pass.
What I'd like you to do now, is go look at the How to Design Functions.
And how to design data, and data driven templates webpages.
And pay attention to the parts that talk specifically about designing with lists.
Just go ahead and review that, and then you'll be in a good position to keep
designing with lists going forward. And remember, the big summary of kind of
what we've seen so far is, if you have arbitrary size information, then you need
arbitrary size data. That requires a well-formed
self-referential type comment. That leads to a natural recursion in the
template. That leads to a recursive call in the
function. You should test the base case first, and
you should always trust the natural recursion.