[SOUND] In this segment we'll start studying lists. Right now we're just going to learn the basic rules for them, and then in the next segment, we'll program with functions that either take lists or produce lists, just to break things into slightly smaller pieces. we've already seen one way to build up compound data, and that was with tuples, and they're a nice contrast with lists. Tuples, even though we can make them as wide as we wanted or as deep as we wanted, touples inside of touples. We still had to pick that size when we were writing the program. So there was no way with tuples, as they take in a number like 10, or n, or x, and then produce a tuple that had that many pieces, because there be no type to write down for that thing, because you don't know the size until you run the program. So lists don't have that restriction. We're going to be able to build lists with any number of elements and we won't be limited by the type of the list. But there's a tradeoff here, and that is that any list we build will have to have pieces that all have the same type. And that's just the rule for lists in ML, and we'll learn in future a segments and parts of the course how to program around that restriction by using other concerts of the language. Alright, so to understand lists just like with tuples, we're going to have ways to build them and we're going to have ways to use them. So let's start with how we can build lists. The simplest list has zero elements in it, and you build that zero element list by just writing left bracket, right bracket. This is itself a value, so the evaluation rule is trivial. The syntax evaluates to itself, and that's the empty list. Now, if you wanted a list with multiple elements in it, you can just write those down seperated by commas. So let me show you a few examples here so I can really write the empy list, and that's its value. You see the type there, quote A list. We'll get back to that in a few minutes. Let's ignore that for now. I could also make a list three, four, five, and that would hold three, four, five. You can see from the type here. It's a list of, of ints, so it doesn't matter how many elements are in it. A two-element list has the same number, has the same type and so does a four-element list, and so on. these are all values because a list of values is a value. But, I could put expressions in here, three plus four seven, like this and it will evaluate each of those. So, this is the list holding a three and then a seven and then a seven. You don't have to have lists of integers you can have list of Booleans as well. So here's a three element bool list, but you can't mix them. So if I had something like three, four plus five, true, than that's going to give a type error, the same way four plus true gives a type error. All the elements of the list have to have the same type. Of course these are just values, I combined a list to a variable and so on. Okay, so there's one other way to build lists, which is very useful, and that's using this colon, colon operation, which I'll pronounce cons, for constructing a list. Cons, C, O, N, S, and here's how it works. All it does is evaluate e one to some value. E2 to some value that is itself a list. And then it makes a list that has one more element than that list E2 evaluated to. Mainly it puts the result of E1 on the front of the list. So if I flip back here, remember, X is this list 789 I could say five cons onto X. Now it produced the list 5789. You can even say six cons don to five cons don to x. The parenthesis would go like this, you don't actually need them. and that would be 6, 5, 7, 8, 9, and so on. Alright? One thing you can't do is something like this, alright, and that just doesn't type check, and that's because we're trying to take a list of integers, namely the list holding six, and put that on the front of a list of integers. And a list of integers can't hold a list of integers. It is a list of integers, so this is the correct thing to do. You can have a list of a list of integers, so I could cons that six onto a list of list of integers, maybe like this. Alright, and now indeed, I have a list holding three lists of integers. The first is the list six, the second the list 7, 5, and third the list 5, 2. Alright, so that's how to build lists, now how about using them. Well, we need a way to access the pieces, and we need to know a way to find out if our list is empty or not, because if you try to access the pieces of an empty list, you get a runtime error. So let's do that test first. There's a function in ML called null, n, u, l, l. Do not think of this like the null in Java or C+++ or any number of other languages. This is a function that takes a list as an argument and returns true if that list is empty and false otherwise. So for example, if I ask null of X, I'll get false because remember, X is not the empty list, but if I ask null of the empty list I get true and indeed if some other list was empty and I asked null of that, I would get true. So, once you know a list is not empty, it's reasonable to ask for its head, the first element of the list, or it's tail, which is the list, which is all the elements except the first one. And these are the two operations we are going to use to access the pieces of the list. So the head function, spelled HD, just takes a list and returns the first element. The tail function takes a list and returns all the other elements. Alright? So these are just functions. So I can just call them like any other functions. So if I ask for head of X, I get seven cause remember X is this example list, 7-8-9. I can ask tail of X, that will give me back the list 8-9. If I wanted the first element of that list, I'd have to ask head of tail of X, then I would get eight. Can ask of course, also get tail of tail of X. That would be the one element list nine. You could also ask tail of tail of tail of X. What's the tail of a one M element list? It's the zero element list. So this is the empty list. Now if you asked head or tail of that, that would type check just fine, that if I actually evaluate this, I get an uncaught exception for trying to take head or tail of the empty list. I get the same thing if I use head. Alright. So that's accessing the pieces of lists. We've really focused here on the syntax and the evaluation rules. So now let's switch to talking a little more of the types of lists and the types of functions for making them and using them. So, just like when we had a tuples, we had a new way of writing types. So int star int was a pair of ints for example. We have a new types for lists. So for any type t, the type t space list describes the values that are lists holding key elements in them. So, as we've seen in the examples, int list is a list of int. bool list is a list of bools, and so on. Now these things can nest, I think I've shown you a little bit of this, if I make a list of pairs events. That's fine, that's an int star int list. It's a list whose elements have type int star int. So I try to do something like cons, three onto that, it won't type check, but if I try to cons a pair of ints onto that, will type check just fine. Alright, so you can nest these things however you want. You could have a list with another list of ints inside of it. I've shown you one of those. You can have a list with a pair in it and where that pair has a list inside of it and so on. All right, but what about the types of the operations I've given you for building lists and accessing lists? So probably the hardest one to understand is the type of the empty list. So I've showed you before, this has the type written quote, a space list. And I always pronounce quote a as alpha, like the Greek letter. So we say that the empty list has type alpha lists. What that actually means is that you can replace that alpha with any type you want. So the empty list can have type int list, but it can also have type bool list, and it can also have type int star int list, and so on. And that's good, because that's what let's us cons three onto the empty list to get an in list or true onto the empty list to get a bool list. So, the empty list is a special thing that can have lots of types. Its type is alpha list that lets it also have type T list for any type T. Alright, so we're going to see that as a theme with these other operations as well. The cons operator also works for any kind of list. The rule is E2 has to have type t list for some t, and then E1 has to have type t, because you have to add something of the correct type onto the list you started with. Then we have our operations for accessing list, testing if they're empty, getting their head, getting their tail, and these really are just functions in ML. So I have their types written here but we can also see that the read eval print loop. So null is just a function. Again, it's nothing like null in other languages, that takes in a list of any type alpha. So for all types alpha, you can take in an alpha list, and we'll give you back true or false. And that's why I can't ask null with a list of integers or with a list of Booleans. In a couple sections later in the course, we'll learn how to write our own functions that have types with these alphas in it, and other Greek letters if you like, but for now we're just going to use ones provided to us by the ml language. Similarly head takes in a list of alphas for any type alpha, and what you get back is an alpha. That's why, if you call head with a list of integers, you get back an integer, and if you call it with a list of Booleans, you get back a Boolean. And finally, tail takes a list and returns a list, alpha list to alpha list, and those two type, lists, have to have the same type, which is why, if I say tail of 3,4, I get an int list back, because I passed it in int list. Alright? So now we know our key operations for building lists and accessing lists. What we'll do next is a very powerful, very common thing in functional programming, which is to write useful functions that take in return lists.
