Now, it turns out you can represent 
arbitrary size information using compound 
date and that's something we'll do a 
little bit later this week. 
But the simplest form of arbitrary size 
data, is lists of values, and so, we're 
going to do lists of values first. 
Now, before I can talk about designing 
with lists, I have to show you the basic 
mechanisms that BSL gives us for 
representing lists. 
So this is kind of like what happened 
last week where first I showed you the 
define struct mechanism, and then we 
learned how to design compound data. 
First I'm going to talk about the BSL 
primitives for lists, and we'll do that 
in this video. 
And then over the next several videos 
we'll look at designing with lists. 
The primitive data that BSL gives us is 
called lists. 
Here's the value that BSL gives us for 
representing empty lists. 
So, that value empty is an empty list of 
anything you want. 
It's an empty list of strings. 
It's an empty list of hockey teams. 
It's an empty list of numbers. 
Since it's empty, it can be an empty list 
of anything. 
Now let's look at how to make a list that 
isn't empty. 
The way we do that is, we have a 
primitive cons. 
And if I do this, that is a list that's 
constructed by putting flames onto the 
front of this list here, which happens to 
be empty, so this is going to be a list 
of one element. 
Here is a list of two elements. 
And again, the way you read this is it 
says well construct a list in which Leafs 
is the first element and then add Leafs 
to the front of constructor list in which 
you add Flames to the front of the list 
empty. 
So that's a list of two elements. 
If we run this, Racket shows us the list, 
using this Cons notation it's called. 
So it shows us values that look very much 
like these expressions. 
But there's an important point to make 
here. 
Let me show you a third one of these. 
kind of a silly one, except to make this 
point. 
If I evaluate this third expression, the 
value that I get is cons, canucks, empty. 
What happens is when rachet evaluates 
this the string append, C, anucks 
produces the string Canucks and then the 
result in value, the resulting list Is 
the list formed with the string Canucks 
at the beginning of the list that's 
empty. 
So, you could put expressions as the 
operands for cons in expressions when BSL 
shows us values. 
It'll always be formed out of values. 
Now, lists can have more than just 
strings in them. 
For example, you could represent problem 
set quiz grades. 
And let's suppose we're doing very well 
in our problem set quizzes. 
So we've got a 10, a 9, and a 10. 
There's a list of three elements. 
The numbers, ten, nine and ten. 
And we can also make lists of images for 
example. 
So we have a list that's a square of size 
ten and solid and blue and let's see, the 
second element of the list would be a 
Triangle of size 20 that's solid and 
green, then empty. 
So lists can have all kinds of different 
values in them. 
Technically you can use the list 
mechanism to make Lists that have more 
than one type of data in them. 
The mechanism will do that, but our data 
definitions don't let us talk about that 
very well. 
So, we're not going to see values like 
that in this course. 
We clean this up a bit. 
And what I'm going to do is give some of 
these values names. 
Let me call this one, l one. 
And I'll call this one, l two. 
And I'll just get rid of this one, and 
I'll call this one l three. 
Now they've all got names. 
Now that we've made lists of things, we'd 
kind of like to know what's in the lists. 
So racket gives us two more primitives 
for doing that. 
One is called first. 
So first given a list, produces the first 
element of the list. 
So first of L1 produces flames. 
First of L2 would produce Ten, and first 
of L3 would produce that square. 
Okay, so that's first. 
First produces the first item in the 
list. 
First is kind of like a selector. 
That's because lists are kind of like 
compound data. 
Right? 
Cons is basically a compound data 
constructor saying, make a new list in 
which the first element is this, and the 
last of the list is the second operand 
For cons. 
So first is a selector that produces the 
first item in the list. 
And the name of the selector that 
produces the rest of the elements of the 
list is called rest. 
So rest of L1 is going to be empty. 
Because rest, everything in the list 
after flames is empty. 
We'll just quickly type these other two. 
Rest of L2 is cons9, cons10 empty. 
And rest of L3 is cons the triangle 
empty. 
So that's first and rest. 
Those are the bsl primitives for taking 
lists apart. 
Now let me ask you a question. 
Suppose what I want. 
How do I get the second element of L2. 
Now, bsl has a primitive called second. 
And, and has one called third. 
I don't want you to use those. 
For the next couple weeks. 
In order to get at the insides of lists, 
in order to take lists apart, and we want 
you to use first and rest. 
So using only first and rest how do I get 
at the second element of L2? 
Well if, if I call first as the first 
thing I do I'm in trouble. 
because I'll just get temp. 
But what I do actually is I take rest of 
L2. 
Now that's going to give me cons nine, 
cons ten empty. 
And once I have rest of L2, then the 
first of that, is the second thing in L2. 
The way to read this is, first of rest of 
l2. 
So rest of l2 is that. 
It would be the first of that, which is 
9. 
How do I get the third element? 
You just do the same trick again. 
You say first a rest. 
The rest of L2. 
Now that would get tedious if you wanted 
to get the twenty third element of a 
list. 
And what we'll see, starting in the next 
lecture is that we do it a different way. 
So let's see, I have cons for 
constructing lists. 
I have first and rest for taking lists 
apart. 
There's one more primitive that dsl gives 
me for working with lists, and that's 
called empty question mark. 
It's a predicate cause it's name ends in 
question mark. 
And what happens is the empty question 
mark of empty. 
Produces - let me comment these things 
out so we won't get confused here. 
Empty? 
of empty produces true. 
And empty? 
of a list that isn't empty or in fact of 
anything at all produces false. 
You can also say if you want empty? 
of one but you're not going to say that 
As often. 
We'll often want to know is the list that 
we're holding here empty? 
So there you go, there's the primitives 
for constructing and operating on lists 
that are part of the DSL language.