In the next few videos, we're going to 
learn how to design with lists. 
That's going to include changes to both 
the how to design functions, and how to 
design data recipe. 
Now, the way I'm going to present those 
changes is different than I used to 
originally cover those recipes. 
What I'm going to do, starting in this 
video, is charge into a data design 
problem with lists. 
And when I get to a place that, I don't 
know what to do. 
That the recipe doesn't already tell me 
what to do I'm going to make a lucky 
guess and it's all going to work out 
fantastically. 
I'll do that with the data recipe in this 
video, and I'll do it with the function 
recipe in the next video. 
And then in the third video, I'm going to 
go back and explain why those lucky 
guesses really were the right guesses and 
formally include them into the recipes. 
So that you'll be able to design with 
lists systematically from that point on. 
This problem has to do with designing a 
program that's going to keep track of 
your favorite Quidditch teams. 
So, we're going to design a data 
definition to represent a list of 
Quidditch teams. 
Remembering always that when we design 
data definitions, what we're doing is 
working out how to represent information 
as data. 
Let me just do a couple comment boxes 
here. 
And in this box, we'll put some examples 
of the information. 
So, I'm going to focus on some of the 
Canadian Quidditch teams, one of which is 
UBC. 
One of which is McGill, and one of which 
is the team Who Must Not Be Named. 
And by that, I don't mean Toronto, I mean 
a team that's actually chosen that name. 
Which I think was a little silly, but 
never mind. 
So, now let's think about the data that 
might be used to represent that. 
You know, those things look a lot like 
strings to me. 
Strings look like a good way to represent 
that. 
So, for example, you might represent the 
team UBC As the string UBC, and, and so 
on. 
So, that's how we might represent some 
individual teams. 
Now, how might we represent a list of 
teams, right? 
A list of my favorite teams. 
Well, we saw how to do that using conses. 
I would say cons. 
Let's suppose that my two favorite teams 
are, those that my favorite teams are UBC 
and McGill. 
That's kind of how we would represent 
that using lists. 
So, now I've thought some about the 
information and the data, and I'm ready 
to go ahead and write out the actual data 
definition. 
So let's see, what I've got here is kind 
of a list of string. 
Every, every element of this list is a 
string, so I'm going to go ahead and call 
the type, list of string. 
Now I could call it list of team, but I'm 
going to call it list of string. 
We'll see some examples where you'd list 
introduce another type name, for example 
team. 
We'll see some of those a little bit 
later this week. 
So, I'm going to say list of string is. 
Now here, there's an interesting little 
thing, which is here's one list of 
favorite teams, and the rest of that list 
is a list of favorite teams. 
And the rest of that list is also a list 
of favorite teams, but it's an empty 
list. 
So, buried in the midst of here is this 
subtle point that empty would also be a 
good example. 
Let's just suppose you didn't like any of 
the current Quidditch teams, your list of 
favorite teams, not with a quote there. 
Empty like that would also be an example. 
So, the way I'm going to write this type 
comment, and again, we'll come back to 
this. 
Remember, I said I was going to kind of 
get lucky. 
A few times in this design and then after 
the data design and the function design. 
I'll explain it all. 
The way I'm going to write this type 
comment is like this. 
I'm going to say that a list of string is 
one of either empty or cons string, list 
of string. 
Now, there's an interesting thing going 
on there, which is in the middle of this 
type comment. 
I refer to the type comment itself, so I 
define a list of string and in the middle 
I refer to the list of string. 
And we're going to talk a great deal more 
about that. 
I'm just pointing out that that is there 
when you see that, that's what I mean to 
say. 
Let's do an interpretation. 
Interpretation, a list of strings, 
because each element in these cons is a 
string. 
And now let's do some examples. 
Well, one example is empty, and another 
example is say, just McGill and empty. 
And another example, oops, that's not 
one, that, that's two. 
And another example is cons. 
UBC, cons, McGill, and empty. 
Before we go on, let's see if the type 
comment we have matches the examples we 
have. 
We're going to talk more about the type 
comment in upcoming video, as I said. 
But, it's a pretty good question right 
now to at least make sure that the type 
comment admits the three examples we 
have. 
So, let's try that. 
The value of LOS1 is empty. 
So the question we have to ask is, is 
empty ListOfString? 
Does empty match the type ListOfString? 
Well let's see, the type definition for 
ListOfString is this. 
And there's two cases, so let's see, does 
empty match the first case? 
Yes, it does. 
So, now we know that empty is list of 
string. 
That wasn't that hard. 
Now let's ask about LOS2, which is cons 
McGill empty. 
Again, we want to ask is that list of 
string? 
Well, here's the type definition for list 
of string. 
And there's two cases. 
Let's see, does cons McGill empty match 
the first case? 
No, it doesn't. 
Cons McGill empty definitely isn't empty. 
Let's try the second case. 
Well, cons McGill empty starts out with 
open parin cons, which is how the second 
case starts out, so that looks promising. 
And cons McGill empty has this closed 
parin at the end, which the second case 
also has. 
So that looks promising. 
Now the question we have to ask is, is 
McGill, is the second thing in cons 
McGill empty, McGill, is that string? 
Well, yes, McGill is string, that's 
trivially true. 
We know that McGill is the string. 
So because that's yes, we get a little 
bit more of a match between cons McGill 
and the second case of list of string. 
Now we need to ask the question, is empty 
list of string? 
Well we've done this before, but I'm 
going to do it again just for 
completeness. 
So we ask the question, is empty 
ListOfString? 
We look at the type definition for 
ListOfString. 
And its listed string is one of there's 
two cases. 
And empty matches the first case. 
So yes, empty is ListOfString. 
So going back into the prior matching, 
that means empty matches list of string 
there and there. 
So, now we have a complete match. 
And we know that cons McGill empty is 
ListofString. 
And I think you can see that this would 
work for longer lists. 
It would just get boring if I had a list 
that had two elements in it, then I would 
end up having to go to list of string the 
first time. 
List of string the second time, and list 
of string the third time to get the empty 
at the end. 
It would just keep going. 
In some sense, what's happening here is 
that this self reference in the type 
comment replacing the type comment with a 
list of string refers to itself is 
letting us match arbitrarily long lists. 
Because we just start the matching over 
with the last of the list, as many times 
as we need to, before we finally get to 
the empty case. 
We'll talk more about this the video 
after this next one. 
Now, let's do the template. 
I'm going to say define fun for, and I'm 
not going to write list of string here. 
For these list of types, we're going to 
let you abbreviate it like this. 
And let's see. 
Template rules used. 
Now, the template starts off easily 
enough. 
First word after is is one of, so the 
first rule is the one of rule. 
And there's two choices. 
So that means I'm going to put in a cond 
with one question, one answer, and 
another question and another answer. 
And that's the beginning of the template. 
Now let's see, the next part is easy 
after the one of isn't empty. 
So, that's an atomic distinct empty 
because empty is a single value. 
There's a single empty list. 
So, atomic distinct empty. 
The predicate for empty is empty question 
mark, and it's an atomic distinct so we 
just have dot dot dot in the answer. 
That's atomic distinct empty. 
Now, we have this case. 
And remember what I said. 
The way we're going to think about a cons 
is of a cons as compound data. 
So, we're going to use the compound rule 
here. 
And if we go look at the data driven 
templates page, we'll see that cons is 
one of the examples it gives for 
compound. 
So it's compound, cons, string, list of 
string. 
It's the last question of an itemization, 
so we can make the question be else. 
And then it's dot, dot, dot and the two 
selectors. 
Well, the selectors are first of los, and 
rest of lost. 
And the type of first is string, because 
it's the column of strings and the list 
of strings. 
So, the type of first is string. 
And the type of the rast is list of 
string. 
Now here, what I'm going to do, and I'm 
going to talk more about this. 
Not in this video or the next video, but 
in the video after I'm going to come back 
to this point. 
So now, I'm going to kind of just do 
something. 
This is what I mean by getting lucky. 
I'm going to do something lucky. 
I won't explain why. 
We'll explain why in two videos. 
But I'm going to put, this in the 
template right here. 
I'm going to run that template. 
There are no errors, so it's well formed. 
We'll comment it out. 
And now, at this point, I can delete this 
scratch work up here. 
And there's a data definition for 
representing Quidditch teams or lists of 
Quidditch teams using lists of string. 
In the next video, we're going to design 
a function operating on these lists.