This course is an introduction to the basic concepts of programming languages, with a strong emphasis on functional programming. The course uses the languages ML, Racket, and Ruby as vehicles for teaching the concepts, but the real intent is to teach enough about how any language “fits together” to make you more effective programming in any language -- and in learning new ones. This course is neither particularly theoretical nor just about programming specifics -- it will give you a framework for understanding how to use language constructs effectively and how to design correct and elegant programs. By using different languages, you will learn to think more deeply than in terms of the particular syntax of one language. The emphasis on functional programming is essential for learning how to write robust, reusable, composable, and elegant programs. Indeed, many of the most important ideas in modern languages have their roots in functional programming. Get ready to learn a fresh and beautiful way to look at software and how to have fun building it. The course assumes some prior experience with programming, as described in more detail in the first module. The course is divided into three Coursera courses: Part A, Part B, and Part C. As explained in more detail in the first module of Part A, the overall course is a substantial amount of challenging material, so the three-part format provides two intermediate milestones and opportunities for a pause before continuing. The three parts are designed to be completed in order and set up to motivate you to continue through to the end of Part C. The three parts are not quite equal in length: Part A is almost as substantial as Part B and Part C combined. Week 1 of Part A has a more detailed list of topics for all three parts of the course, but it is expected that most course participants will not (yet!) know what all these topics mean.
List Functions
Loading...
From the course by University of Washington
Programming Languages, Part A
818 оценки
From the lesson
Section 1 and Homework 1
It's time to dive in! Start with a careful reading of the "Section 1 Welcome Message" and go from there.
Meet the Instructors
Dan GrossmanProfessor
Computer Science & Engineering
[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.
Ознакомьтесь с нашим каталогом
Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.
Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.
© Coursera Inc., 2018 Все права защищены.
