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.