Functions as Arguments

Loading...

來自 University of Washington 的課程

程序设计语言

817 個評分

University of Washington

程序设计语言

817 個評分

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.

從本節課中

Section 3 and Homework 3 -- and Course Motivation

This section is all about higher-order functions -- the feature that gives functional programming much of its expressiveness and elegance -- and its name! As usual, the first reading below introduces you to the section, but it will make more sense once you dive in to the lectures. Also be sure not to miss the material on course motivation that we have put in a "lesson" between the other videos for this week and the homework assignment. The material is "optional" in the sense that it is not needed for the homeworks or next week's exam, but it is still very highly encouraged to better understand why the course (including Parts B and C) covers what it does and, hopefully, will change the way you look at software forever.

與講師見面

Dan Grossman
Professor
Computer Science & Engineering

[MUSIC]

In this segment, let's get right to studying probably the most common use of

first class functions which is passing one function as an argument to another

function. So, I want to emphasize that there's

nothing really new here in terms of language features, we just never thought

to do this before. So, we could define a function binding in

ML, say, f that took as one of its arguments another function g. And then

inside the, the body of f, g would be a variable.

That when we look it up, we get a function.

And so, we could call that function with some arguments.

And so, we could use f in one place calling it with h1.

And in another place, calling it with h2. So, that makes f more useful, more

parameterizable because different callers of f can pass in different functions.

This is going to be a very elegant strategy for us.

We're going to be able to take common pieces of code and abstract them out

which is one of the best things to do when you're designing software.

And the way we can abstract them out is instead of having n very similar

functions, we could have one function that has all the common parts and then,

pass in n different shorter functions that just describe in their bodies and

their computations the parts that are different.

So really, the rest of this segment is going to be over in Emacs showing you a

good example of this, a simple example of this to give you a sense of how this

might work. So, to start with, I already have written

here three ordinary non higher-order functions.

Plain old first-order functions, we call them.

but they all have quite a bit of similarity, which we'll see.

So, they're a little silly, but bear with me.

This first one just takes two arguments n and x and increments x, n times.

So, if n is zero, it just returns x. Otherwise, it returns one, plus the

result of incrementing x, n minus one times.

Now, this really is quite silly. This is an addition function.

It's just taking x and adding n to it, but, but that's okay.

The second example is a bit less silly. There's no built-in operator for it in

ML. It takes a number n and another number x

and it doubles x, n times. Put it another way, if you're a little

more familiar with your math, it's two to the n times x, alright?

And the way it does it is it says if n is zero, return x.

Otherwise, multiply by two the result of doubling x, n minus one times.

The last example doesn't necessarily work with numbers at all, it works with lists.

Takes a number n and a list x's and it takes the nth tail.

So, for example, if you pass it three and the list 4, 8, 12, 16, then you would get

back the list 16. Because if you take tail of tail of tail

of that input list, you end up with the list holding just 16,

okay? How does it do it?

If n is zero, then just return the entire list.

Otherwise, take tail of the nth tail of n - 1 and x's.

Alright. So, three simple functions we could have

already written ourselves. But hopefully, it pains you to see so

much similarity between these functions. All of them take two arguments.

If the first argument is zero, return the second one.

Otherwise, do something to the recursive call with x or x's and n minus one.

So, somehow we'd like to separate all this out so we don't have to write all

that stuff three times. And in general, these might be bigger and

more complicated. and the only way we can do this without

first class functions which would be some ugly kluge, where we had some flag.

Do I want to be increment or double or nth tail?

And that's not extensible. What if there's a fourth function that

comes along that is like this? But first-class functions do this very,

very well. So, what I'm going to do is write a

function n times. That, in addition to taking n and x,

takes another argument, f. And that f is going to capture the

differences between the three functions above.

So, in every case, I want to say, if n0, = 0, then just

return that second argument. Otherwise, I definitely want to call n

times with the same function n - 1 and x. And then, what I want to do to that

recursive result, well, that depends.

And it depends on whether I want to do doubling or incrementing or tailing.

but in all cases, we'll just have the caller pass in an f that does what we

want. So, that is our useful higher-order

function and now let's see how we can use that to do incrementing and doubling and

tailing. And so, let me first just define a couple

very simple and very short helper functions like this.

There are various ways you can double there's one, right?

And now, what I can do is use n times in various ways. So, if I wanted to double

seven four times, then I would just do that.

And if I, oops, sorry. x1 equals, there we go.

if I wanted to increment seven four times,

then how about I make the exact same call, but I pass an increment instead.

And similarly, if I wanted to take the tail,

so maybe two tails of a list like 4, 8, 12, 16, it'll work just like that.

And sure enough, if I come over here and run it,

functions as arguments.sml. You'll see that x1 is 112, x2 is eleven,

and x3 is 12,16. So, we saved a lot of code reuse here.

We got a lot more code reuse. All we did here was use n times,

increment double, which are very short and then, use it in different ways.

Now, you might be thinking, well, that's great.

But, you know, callers, you know,

users of my code shouldn't have to go to this extra work.

But, of course, they, they don't have to, right?

If I want to write my own increment function that takes n and x.

And how about I change its name, since we know this is really just addition.

As long as n is greater than or equal to zero,

none of these functions work for negative n.

I can just define this like this, right?

The function that takes n and x and increments x n times can be implemented

by calling n times with increment n and x.

And similarly, double n times could be better written as this body.

[SOUND] And finally, nth tail, n, x can be written as this.

And as always, callers of these functions don't need to know and don't need to care

that we've implemented them using the same common code, n times, under the

hood. And then finally, suppose we did this, we

are very happy with ourselves, we can now go up and really get rid of or

for the sake of simplicity, I'll just comment out all this repetitive code.

So, all we have now is n times and these three helper functions, and then maybe

sometime later, you'll realize that that pattern,

that reusable code, that higher-order function n times is

even more useful. Maybe you come along and you realize that

oh, you need to triple some number n times, n, x.

And you're like oh, well, I'll just call n times with a

little helper function triple that I'll write and n, x.

and, of course, I need to define triple here.

And it'll be three times x, alright? And this is all wonderful.

and let's go back and make sure we got that all right.

And sure enough, what we now have are functions additional, addition and double

n times, both of int star int arrow int. We have nth tail of type int star alpha

list arrow alpha list and triple n times of int star arrow int.

So, n times which fundamentally just takes a function and an n and an x and

ends up returning f of f of f of f. N times of those applied to x is a

generally reusable, beautiful high-order function that we can reuse by passing in

different functions in that position for f.

So, that seems like a great example. The only thing that might be a little

confusing to you is this type of n times which looks a little complicated in

polymorphic. And so, let's talk about that a little bit more in the next

segment.

探索我們的目錄

免費加入並獲得個性化推薦、更新和優惠。

Coursera 致力於普及全世界最好的教育，它與全球一流大學和機構合作提供在線課程。

© 2018 Coursera Inc. 保留所有權利。

通過 App Store 下載

通過 Google Play 獲取