Partial Application

Loading...

From the course by University of Washington

Programming Languages, Part A

816 оценки

University of Washington

Programming Languages, Part A

816 оценки

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.

From the lesson

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.

Meet the Instructors

Dan Grossman
Professor
Computer Science & Engineering

[MUSIC] In this segment, we're going take curried functions and call them with too

few arguments and see why that's a neat thing to do.

So previously we used currying just to simulate multiple arguments.

If you wanted a three argument function We used currying to have a function that

returned a function, that returned a function to have three arguments.

But, what if we took those same function definitions and as callers just passed in

fewer arguments, one or two, instead of three.

Well then what we would get back, is a closure.

That's waiting, if you will, for the remaining arguments.

There's no new semantics here, it's just a pleasant idiom that is completely

allowed, you can always call a function that returns another function, and then,

save that function and have it around, for when you want to call it.

So this is called partial application. It's very convenient and useful.

You can do it with any curried function, and I'm now showing you any new language

constructs here. So let's do a couple examples, I've

already written out all the code for this segment.

So we have our two curried functions from the previous segment.

We have sorted three which takes x, y, and z curried, and fold which takes f,

acc, and xs curried. And now let's notice Then we can just

call sorted3 with 2 arguments instead of 3.

So we're going to call sorted3 with 0. That will give back a function, we'll

call that with 0. We'll get back another function and then

when we call that function what we'll end up doing is taking in an argument z and

asking is z>=0? And is y, is 0 greater than or equal to 0.

So fundamentally, what we got back was a function that takes in one argument and

tells you if it's non-negative. Well, that's not the most useful function

in the world, but it helps out something actually useful, like summing up all the

elements in a list. Here I have a call to fold where I've

also passed in 2 arguments instead of 3. So what I'm going to do is get back a

function that expects a list x's. Right? It'll basically be this function

here and we'll fold over it using this for fn its environment and this for the

initial accumulator. So this will actually sum all the

elements in the list. Now there are other ways, perhaps more

intuitive to you before you've seen this. Technique ways to write this function.

I could write is_nonnegative by just being a function that takes in x and call

sorted3 with 0 and 0 and x or sum all the elements in the list, the same way I

showed you in the previous segment where we just create a function that takes in

xs And calls fold with these 3 arguments. It's just longer, right? These are

pleasant, we get used to it, it's a convenient thing partial application.

These are not terrible, this is not awful style.

But we want you to get some practice with the sh.

Shorter way, that demonstrates that you understand how currying and partial

application work. And in fact, if I go back to the slides

here quickly, the reason why the second version is really the same as the first

version, is actually something we've seen before.

Just a little bit different. This top version, is just unnecessary

function wrapping. Right? We, have seen before, that, we

shouldn't write fn fx = g(x) when we can just write val f = g.

Well its the same thing here, except instead of having the variable g for the

name of the function. We have the function that you get, by

calling fold with the synonymous function.

And zero. Alright? So let me show you a couple more

examples I have here of just currying and partial application being useful to

hopefully get the hang of it. Here's a function range which takes two

arguments in a curried form. And essentially if you call Range with

something like 3 comma, sorry, not comma. We're not toppling.

Range 3 6, that produced the list 3, 4, 5, 6.

Something like that. All right? And so if you call range with

just 1 number, like, say 1 That's going to give a function back, that when you

call it with a number, returns from the one up-to that number.

And so, count up of, 6 where we return to the left 1,2,3,4,5,6.

Just another example where we didn't need this unneccessary function wrapping

version that you have here. The function range 1 is a perfectly good

function, we can just say val countup = range 1.

As a more useful example are iterators. Are higher order functions over lists and

data structures like that, are often written in a curried form.

So let me show you another example, just to sneak in another useful iterator.

Here's a high order function exists, that takes a function which I'll call

predicate, and a list xes. And returns true.

Returns true, otherwise it returns false. So there's a simple 3 line function.

The empty list should return false. There does not exist an element of the

list for which predicate is true. Otherwise it's predicate applied to the

first element of the list Or there exists some element in the rest of the list for

which predicate returns true, so that's exists.

Here's a use of it. If you call Exist with a function that

checks whether its argument is seven, and a list that does not have seven, you will

get false. Alright so that's the result here, is

false. But much more interesting, is to take

Exists, and partially apply it. A way applied to one argument will get

back a function that takes a list and returns the book.

So has zero does indeed have type int list arrow book and when your call has

zero within int list, itwill check wether any of the elements in the list are zero,

because exists with this anonymous function returns the function, Returns a

closure, that given a list, checks what we want to check.

Similarly, the, build in library functions in the list library provided by

ML's standard library, are often written in curried form.

So list dot map is actually defined for us, but it's curried.

So if you call it with fun X, arrow, X plus 1.

You get back a function, int list arrow int list, that will, indeed add 1 to all

the elements in the list, returning a new list, and List.filter works the same way

in the standard library. If I call it with this function, I will

get back a list that is also an int list arrow int list, is the type of

removeZeros, and the list I get back will have all the zeros.

Removed from it. So that's very elegant and when you go to

use these functions you have to use them in a curried form here we're using

partial application. but there is one thing that I don't want

to talk about right now. But unfortunately I have to.

So once you start using these polymorphic curried functions with partial

application, you might run into this thing called the value restriction.

The value restriction is something that's NML for very good reasons, the type

system would be broken without it. I don't really want to talk about it

right now, 'cuz it's confusing. But you may start seeing something like

warning type vars not generalized. And if you see that warning about some

partial application that you have, you're not going to be able to use the function

to get back. And this shouldn't surprise you have not

actually done anything wrong in terms of what I have taught you so far, but you

simply have to work around it. And you know no language is perfect.

This is an ugly fact of life in languages like ML.

So let me show you an example that might happen.

Use partial application all that you want for now, it's a beautiful item.

But if you do something like this. Where the result would be a polymorphic

function. So I'm going to map this across

something. So this could take any, the resulting

function could take any kind of list and would return an alpha star int list, of

the same length where I put a 1 next to every element of the list, and this will

give that weird warning. And, it won't be able to be called, and

how should you work around this? Well, the first way is to just, give up on the

partial application, and put in, what I said was unnecessary function wrapping,

but now it's a little more, necessary. If you don't like that, and you really

want to do partial application, then you can put in an explicit type.

That's not polymorphic, like this, and then you have a perfectly fine function

but it can only be used with string lists, not with any kinds of list.

I should also point out, that on homework 3, and things like that, you are not

likely to run across this, because it only happens when the resulting function

would be polymorphic. So for example, this call will not give

any kind of warning, because we can tell from this anonymous function That it can

only be applied to int-list anyway. So, just wanted to talk about that,

didn't really wanted to, but in case you hit the warning, I didn't want a bunch of

questions, of that thing you told me to do isn't actually working.

It usually works, when you get the value instruction for things like List.map,

I've given you a couple of work arounds.

Ознакомьтесь с нашим каталогом

Присоединяйтесь бесплатно и получайте персонализированные рекомендации, обновления и предложения.

Coursera делает лучшее в мире образование доступным каждому, предлагая онлайн-курсы от ведущих университетов и организаций.

© Coursera Inc., 2018 Все права защищены.

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

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