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.