Explore
For Enterprise
Join for Free
Log In

Гуманитарные науки и искусства
Бизнес
Компьютерные науки
Наука о данных
Информационные технологии
здоровье
Математика и логика
Личное развитие
Естественные и технические науки
Социальные науки
Изучение языков
Степени
Сертификаты

Полный обзор Coursera

Обзор
Поиск
Для организаций
Войти
Присоединиться бесплатно

List Functions

Loading...

Programming Languages, Part A

Вашингтонский университет

4.9 (оценок: 1,041) | Зарегистрировано учащихся: 63K

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.

Просмотреть программу курса

Получаемые навыки

Recursion, Higher-Order Function, Pattern Matching, Functional Programming

Рецензии

4.9 (оценок: 1,041)

5 stars
982 ratings
4 stars
52 ratings
3 stars
1 ratings
2 stars
1 ratings
1 star
5 ratings

VA

Mar 05, 2018

Very interesting course! Superb teaching and homework assignments. If you are interested in functional programming or in programming languages in general, this should be one of the must take MOOCs

MK

Jun 17, 2017

Good fundaments for learning new programming languages. Well prepared and challenging homeworks. I learned a lot of functional programming concepts fom this course and I am sure I will use them.

Из урока

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.

ML Variable Bindings and Expressions14:32

Rules for Expressions9:13

The REPL and Errors12:11

Functions Informally7:37

Functions Formally8:56

Pairs and Other Tuples9:16

Introducing Lists10:34

List Functions11:21

Let Expressions7:51

Nested Functions7:38

Let and Efficiency10:10

Booleans and Comparison Operations7:00

Benefits of No Mutation7:24

Optional: Java Mutation4:44

Pieces of a Language6:02

Преподаватели

Dan Grossman
Professor

Текст видео

[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., 2019 Все права защищены.

Загрузить из App Store

Загрузить в Google Play

Coursera
О проекте
Руководство
Карьера
Каталог
Сертификаты
Сертификаты MasterTrack™
Степени
Для организаций
Для правительственных организаций

Сообщество
Learners
Partners
Developers
Beta Testers
Translators

На связи
Блог
Facebook
LinkedIn
Twitter
Instagram
YouTube
Технический блог

Еще
Условия
Конфиденциальность
Помощь
Доступность
Пресса
Контакты
Справочник
Филиалы