[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.