Tip:
Highlight text to annotate it
X
. 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 fa
ct 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 e lement 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 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 simpl y 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. And then added that to summing . 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.