[SOUND]. In this segment, we're just going to write a bunch of functions that either take lists as arguments, or return lists as results. We're not going to learn any new language constructs. Instead, what we're going to do is take our understanding of how recursive functions work, as well as, as well as our understanding for how lists work. And combine them very powerfully to write a lot of real useful programs, actually. And functions with very little code. All right. So let's just go over here and get started. How about as an initial example we write a function to add up all the numbers in a list. So, let's just take one argument of type int lists, I'll call it Xs, this is just a convention to give variables that hold lists names that end in s, like the X's where each element in the list ends in an x. But it's just a variable name, nothing more or less. And now we just have to add them up. Now the key thing when you're processing a list, is to ask what should I do if the list is empty and what should I do if it's not empty. Well, now if it is empty, maybe you think that's not a well defined question. It's perfectly well defined. The sum of zero elements is zero, alright. that's going to help us out for our recursion, it's also what mathematicians will tell you is the proper sum over an empty collection. But, in any case, let's just now handle the non-empty case. So, the way you sum up the elements of a non-empty list, is you take the first element. And you add to it. The sum of adding up. All the other elements. So take the tail of the list, sum that up to get a number, add to that the head. It's a simple recursive thought that follows directly from understanding what should I do if the list is empty, what should I do if the list is not empty. So this is a good example of a function that processes a list. How bout we look at this for just a second. Make sure it works. You see indeed, that it's type is, it takes a list of int's and it returns an int, and we can try it out with for example, with three, four, and five, and get twelve. Alright, very good. So that was an example of a function that took a list and returned here a simp, single answer like int. How about a function that takes that has kind of the opposite type that takes an int and returns an int list. And what I want to do actually is if I call this for example seven, I want this to return seven, the list, excuse me seven six five four three two one something like that. that's just the function I want to write. all right? So now, I have a different recursive question. I want to say, well, when, should I stop making a bigger list? Well, that's if x is zero. So if x is zero, then let's just return the empty list. That's how you count down from zero. You just have no more list. otherwise let's put x on the front of some smaller list. And in fact, the list you would get from evaluating the expression. Call countdown with x-1. All right. So that's that. Let's go over here and try this out. And indeed, countdown takes an int and returns an int list, and I could say, countdown of seven. And I get seven, six, five, four, three, two, one. By the way, if you say count down to seven hundred, it will do the right thing, but the redevelop print loop is trying to be nice to you, and figuring that you don't want to see the entire answer, so you'll notice this dot, dot, dot, here in the buffer. it really is a seven hundred element list, and I could actually prove that to you by calling sub list on count down of seven hundred, and I'll leave it to you to verify that it produced the correct stuff. Alright let's go back here and write some more functions. Here's probably one of my favorite ones, this might look familiar and I'll tell you why in just a second. Let's take two ent lists and append them so to return a new list that has all the elements of X, X's followed by all the elements of Y's. Now we'll learn later how to define this in a way that works for any kind of list not just an ent list but we'll keep it simple for this segment. And boy that seems like a tough thing. In fact this is sometimes even an interview question if you're using a language like C or Java. But, let's just think about how we would do this recursively. We could think well, iff the first list is empty, Then it's really easy to put all the elements in the first list in front of the elements in the second list. there aren't any. So just return Y's. Otherwise, what would we do? Well what I could do is that I know the final result is going to start with the first element of the first list, and then I'm going to have to pons that on to some other list. So, how am I going to get all the rest of the elements of the first list appended to the second list? well all I have to do is call append, because that's how I append things. With the smaller arguments, and this isn't going to be an infinite loop or anything. and then wise and that's it. Some of these parentheses aren't needed. But that's exactly the idea. You append a non-empty X's by taking the first element of X's and ponsing it on to the result of the pending the rest of X's onto Y's. And I promise to tell why this might look familiar, this is the first half of the course logo is an implementation of this append function. let's look a the type of this I'll just tell you, you can type it in the rupple and see. This is going to take two int lists. And it's going to return an end list. That's what we would expect from pending two end lists together. Alright, so now, lets write some functions, over pairs of lists. Especially, since on your first homework assignment you'll have to write a number of functions over lists that have triples in them. So int star, int star int. So this will be somewhat similar. So what if we wanted to take a list of pairs of ints. Like this, and add together all the ints in the whole list, including both components of the pairs. Well, if there is nothing in that list, then we'll get zero. That's still the right answer for the empty list. Otherwise we need to take hash one of the first element of the list, add to that hash two of the first element of the list, and add to that. Some pair list tail of X's. This makes perfect sense because if I do, for example, head of X's, that'll give me back an int star int, and then I can do hash one or hash two to get the actual int sum. If we wanted to test this out, we would have to call it with something like sum pair list three comma four, five comma six. And hopefully if we tried that out, we would get eighteen. Alright? Here's another interesting function about firsts. So this is also going to take an int star int list. And what I want to do is return the first component of everything. So, for example, if I called it with this, list of pairs. Three, 4-5, six. I would want to get back the list, three, 5.'Cause that's the first component of each thing. Well, if I start with the empty list, the list holding the first component of everything, is the empty list. Otherwise I have a non-empty list, then I'm going to take the first component of the head and pons that onto the first component of the terrible lists. So, for example if you called this with three comma four five comma six, you're then making a recursive call with the list holding a single pair of five comma six. So that would come back with the list five. By the way, and here I'm going to do a little bit of cut and paste in the interest of time. We can compare this to the funge [INAUDIBLE] seconds. Which just looks like this. And it's exactly the same. Except we do have a hash two right there. And, of course, our recursive call needs to call seconds instead of firsts. And probably a little later in the course, we'll see nice ways to, not have to copy code like that. To be able to write first and seconds, in terms of the same helper function. But for now, we can at least see that, if we applied this to our example, we would hope to get, four, six. And then lastly, I would point out that one of the nice things in functional programming, or really any programming, is sometimes you notice that some of the functions, functions you want to write can be done quite simply in terms of functions you already have. So, I thought I would show you another version of summing pairs of lists. So I'll just call it sum pair list two so that I'm not shadowing my earlier one. Remember this was the thing that took our example list and returned eighteen. It just added everything together. And I would argue. I'm going to maybe try to show you everything at once here. That these three funct-, three of the functions I've written earlier, exactly what I need. Up at the top of the file, the very first function I wrote knows how to sum all of the elements in a list. So what if I called that with the first elements or the components. [SOUND] And then added that to [SOUND] summing [SOUND]. All the second components. Alright, and then I would have a sol, solution to that. So let's go over here try these things out. You can try it out at, whoop. on your own as well. Oop, second seconds, right here on the last line, all right. Much better. And for example, I could call sum pair list two, on three comma four, five comma six, and since I'm feeling bold here. How about nine comma negative three, and I get 24, all right? So that's a bunch of examples. Let me put back to the slides here just to talk a little bit more about recursion and to remind you that it's not surprising that functions of a list are pretty much always recursive. If you're given a list, and you want to implement some function that accesses all the elements. The only way you're going to be able to get to all those elements is with some sort of recursive processing of the tail of the list. So you just ask yourself, what should the answer be for the empty list? And how can I compute the answer for the non empty list, in terms of the tail of that list. That's all there is to recursion. There's nothing magical about it. Similarly, if you want to produce a list whose length depends on some argument you took, like in our countdown example where I am going to put seven, six, five, four, three, two, one, you're going to need something recursive so that you can create your final result out of some smaller list that you created via recursion. Alright. So that's a lot of practice. You can get a lot more practice on homework one. And now we'll move on to some more language concepts.
