[MUSIC] In this segment, I want to continue studying how Racket is a
dynamically typed language by telling you the truth about this cons primitive that
we have been using to build lists. And that truth is that we can also use
cons to make a pair. In fact, what cons really does is take
two arguments and make a pair and in Racket, as is common in dynamically typed
languages, all a list is, is some number of nested pairs that ends with the empty
list, that ends with null. So, it's probably easiest to see that by
just writing some code or using some code that uses this feature.
So, on this first line here, where I'm defining this variable pr, this is just a
pair with 1 in the first position. And in the second position another pair
that holds true and hi. So, this is not a list.
This is the sort of thing that in ML, we would have written as 1,true,hi, spelling
true correctly. but in Racket, we write it like this with cons because we use
cons to build a pair instead of comma and we can see how this will print in the RPL
by just writing pr and you see that what it actually does is it looks just like a
list except it puts this dot before the last element that says this is not a
list. This was the value that you get from
using cons with 1. And then, 1 more pair of cons with true
and hi. But let's compare that to the variable on
the next line, list. So there, I also use cons, which builds a
pair from 1. And then another cons, which builds a
pair from true, and then another cons.
And then, the last one is the string hi and null.
And that does make a list because a list is just some number of conses where the,
where in the cdr of each one, in the second position of each pair, you have
another cons until you get down to null until you get to the empty list.
So, that is what I mean by lists are just a particular kind of nested pair.
So, once we understand this, we see that cons just builds a pair.
In Racket, it's common to call them a cons cell.
And the you access the pieces of a cons cell is with car and cdr.
So, it turns out that car is really like MLs hash1 and cdr is like ML's hash2.
And that is all that is going on. So, given our pair value which remember,
is just nested pairs which prints slightly funny, if I take the cdr(cdr
pr), that gets me the string hi. It's the second component of the second
component. But if I had my list, and I said of cdr
sorry, of list, well then, I get a one element list back, because the cdr of the
cdr of list, is this pair of hi and null. If I wanted the actual hi, I would have
to take car of that, because if we take car of a pair, you get a string hi.
By the way, sometimes in Racket, we find ourselves writing car of cdr of cdr, and
for a long time in Racket and before its Scheme, there's a bunch of built-in
library functions that combine this So, you can use caddr.
And that is how it's pronounced. And all that it is, is there's a built in
function caddr that takes an x and returns car of cdr of cdr of x.
We could have defined this our self. But it's predefined for us in the
standard library. So now, we know the difference between
lists and pairs. As you might imagine, we have built in
functions for asking, do you have a list or a pair.
So, if we ask, is pr a list, the answer is false.
The only things that are lists are the empty list and cons is where you
eventually get down to the empty list. On the other hand, pr is a pair.
Anything built from cons is a pair. And if we do ask about list lst, that
variable, that is a list and it's also a pair.
So here, I'm just using the and primitive,
where I can ask a bunch of questions. I'll get the result true if they're all
true. So, that is our introduction to pairs
versus lists. I should warn you that there are a number
of built-in functions, like length, which works just fine on lists.
If I pass it a list with 3 elements,
I get 3. But if you try to pass it something that's not a list, even if it's
built from cons, you get an error message.
This error message is introducing a little bit of terminology.
Sometimes when we want to emphasize this distinction, we say that lists like lst
are proper lists, whereas something like pair, which is built from cons, but
doesn't end with null, we would call an improper list,
okay? So, that is the code I wanted to show you, lets go back quickly to the
slides. And ask why does, do we allow this, why
does Racket have this? Well, we know pairs are useful, they were useful in ML
and if you earn a dynamically typed language that isn't going to have a type
checker that distinguishes lists from pairs, then why have one kind of way to
build a pair and another kind of way to build a list.
Lets just use the same thing, in Racket's case, cons for building both.
So, in, unlike in ML, we don't need the comma for building a pair and the colon,
colon for building a list. Let's just use the same thing for both,
and programmers will just have to keep track of which things are proper lists
and which things are not. Now as a matter of style, if you have a
collection of unknown size, I don't know how many numbers I need to pass to a
function or something like that, you really should use a proper list.
That's the convention. That's what we want.
Put null at the end of your lists. But if you really just need a quick pair
or a triple, I just need to hold three things, then a pair or a pair with
another pair inside of it is perfectly fine.
We don't have triples built in to wreck it.
You really do have to say something like, let me just go back here, cons 1 of cons
of true onto hi. That would be a fine way to build
something that is like a triple, although it is really a pair with one thing in the
first position and then another. We could have just as well done it this
way, although this is a different data structure and it will print differently,
excuse me. One too many parantheses.
There we go. And this shows that we have an improper
list, we have a pair.
That's what this dot shows with hi in the second position and the pair 1 and true
in the first position and we can get the true out, for example, with let's see,
let me first define this to a variables so it's easier to see what I'm doing.
and then just say how about the cdr of the car of x abd that would be that true,
okay? So, this is perfectly reasonable when you
just need a small number of things, but as we'll see in the next section Racket
has some support for defining our own each of types and I would argue that's
even better style than just using cons which is hard to keep track of how you've
organized things and where things are defined.
And as we saw, in the RPL, as I was playing around with this, the list?
predicate built into the language returns true for proper lists, including the
empty list but not, it returns false for improper lists.
Whereas, the pair primitive returns true for anything made by cons.
And so, that includes all proper lists except the empty list and it also
includes any sort of pair.
Dan GrossmanProfessor
