[MUSIC] We continue our introduction to Racket by learning about Racket lists. This will go quickly because Racket lists work a lot like MLs lists. In particular, the way we used ML lists in section one where we used the functions to access the pieces of a list. So let me just go over the primitives and then I'll write some examples, and again because it works a lot like an ML, I suspect this will not be too surprising. In fact, it will be reassuring to see some of the same ideas in a different language. The way we write the empty list is with the word null. In ML, we would have written bracket bracket, the empty list we write null. It's fine. By the way if you have seen scheme, this is different. In scheme, you often wrote it parenthesis parenthesis, that will not work in Racket. We will use null to write the empty list. If you want to build a list, use the function cons. It won't surprise us the name Racket, that's going to come first before the two arguments just like plus comes before the arguments to plus. This is what in ML, we wrote with colon, colon between the two arguments. So cons will take an element in a list and create a list one element longer. If you have a list, and you want to get the head, use this built in function car. And if you want to get the tail, use this built-in function cdr, spelled C-D-R, pronounced cdr. This is what in ML was the head function hd. And the tail function tl. And finally, to see if a list is empty or not, we can use null? which we often just pronounced null or if you prefer null. And this is what in ML was the null function, N-U-L-L. So perhaps little confusing that we write the empty list N-U-L-L and asked if a list is empty with the null? function, but every language has it's different names for things. Just a couple of more things on the slide that you see here. If you wanted to build a long list, you don't have to say cons of three, of cons of four, of cons of five. There's a provided function list that takes a bunch of arguments and makes a list out of these arguments. So if you pass at en expressions, it evaluates those en expressions and makes a list of length en. We had similar built in, in fact syntactic sugar and ML for when we wanted to do this. And finally, I should talk about these names car and cdr. Why on earth would you have the function for accessing the first part of a list we called car and the rest of the list cdr? Don't try to figure this out in terms of English. It's a historical accident going back several decades, and some of the original machines that this sort of language was implemented on, these things should not be called this but it's too late we're stuck with them. Okay, so that's everything we need but it will make a lot more sense after we just write a few functions, simple things like were it used to. So lets first right a function. I have a comment here, sum all the numbers in a list, okay? So remember, I could define a variable sum and then lambda taken a list xs. I prefer instead the syntactic sugar version of doing exactly the same thing, so I added that parenthesis and then the arguments. This is a one argument function, and now at this point we are very comfortable at the recursive solution to this function. If the list is empty, so I'm calling the null? function with my argument, then 0, it's the second argument to if. The 3rd argument to if will be a function car, call the function plus with the result of calling the function car on xs. I.e., the head of the list with calling sum recursively with the cdr of the list, okay? So that's the end of the called a cdr, the end of the call to sum, the end of the call to plus, the end of the if, and the end of the define. If you're not use the languages like this, you might find it funny that I ended with so many parentheses. It's incredibly natural, you get used to it. It's exactly that I have to finish all these calls and then I have a perfectly good syntactic function. And I could go ahead and run this, and try sum of how about the list with 3 4 5 6, and I would get 18, okay? No problem. By the way, we'll talk about this much, much more, but if you do something like this, this would quote on quote compile because there's no type checker to stop us. But we'll get an error and DrRacket even tries to tell us where this error occur in the code, and it's says that plus expects a number and you gave it a string hi, okay? So that's our first example of a list function. Let's do a couple more. You know my favorite which is append. It turns out append is built into Racket. We could shadow it but I find shadowing confusing ,so how about I call it my-append taking into lists xs and ys. By the way in the previous segment and this one, you'll notice I sometimes have hyphens in my variable names or here in my function name. That's perfectly allowed in Racket, it's just a syntactic thing to get used to. In many languages, we prefer to write it like this or like this. All of these work, it's just a bit more of the convention in Racket to separate the words of our variables and function names with a hyphen. Every language is entitled to its own conventions. Okay, my-append is a function that takes two lists, xs and ys. If xs is empty, return ys otherwise cons, the first element of xs, on to the result of appending the rest of xs on to ys. It was beautiful in ML, it's beautiful in Racket. Let me show you those closed parentheses again, finish the recursive called my-append. There were call to cons, the conditional, and the define. This will work great, so that's append. And let's do one more, how about map? So we see something with a higher order function, works just fine. Again, this one is built in, so how about I call it my-map. Map as an ML takes in two arguments, f and xs. Remember in Racket, this is really a two argument functions, so this isn't toppling or carrying. And we know how map should work. It should apply after every element of xs and return a list of the same length with the result of those calls. So if you have a zero length, zero list, you end up with null, all right? So I asked here, is xs null? If it is, I want to return the empty list. I could have written xs here, but I wanted to show using the null value, okay? The variable null is essentially bound to the empty list. Otherwise cons f of car of xs. All right, so what have I done so far? I got the head of the list and I called f with that head of the list. So that's my first argument to cons. And then my second argument to cons, I can hit return here if I want it to indent nicely. Is to call map recursively with the same f and the rest of the list. And the call to cdr, call to my-map, call to cons, the if, and the define. Okay, so that's map and we can run all this, and we'll see if we do that I do now have a function my-append. The ripple will say, that's a procedure. The same way ML likes to say that's a function. I'm not going to print anything else out for you. My-map is also a procedure. If I try to call my-map with just one argument like lambda x plus x1, this will be an error, and that's because my-map expects two arguments. But, okay, let's go ahead and call my-map with two arguments. In fact, let's define a variable foo to be the result of calling my-map with this little anonymous function, plus x and 1. So what I've written just here, you see highlighted in the gray, is just an anonymous function. Takes in one argument, x that it's in its own parentheses and the function body is a call to plus with x and 1. And then for my second argument to my map, how about cons 3 onto cons 4 onto cons 5 onto null. Of course I could have used the list function to write this more concisely but I want you to get used to lots of parentheses. This is not hard to read. That's the list containing 3, 4, and 5. Close the call to my map, close the call to define, hit return. That worked just fine. The ripple doesn't tell us anything. It was happy to do that definition, but if I asked to evaluate foo, it will tell me that that is the list 4 5 6. The way the ripple prints lists, is with this quote, and then the list elements. And that's fine that really is the list (cons 4 (cons 5 (cons 6 null) and we'll see that because if I evaluate this, I will get the same thing printed by the ripple. So that's our practice with list functions, again they work a lot like in ML. They're just as convenient and powerful, recursion is just as useful.
