DOC PREVIEW
UW CSE 341 - Lecture Notes

This preview shows page 1-2 out of 5 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 5 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

CSE341, Fall 2011, Lecture 7 SummaryStandard Disclaimer: This lecture summary is not necessarily a complete substitute for attending class,reading the associated code, etc. It is designed to be a useful resource for students who attended class andare later reviewing the material.Lectures 7, 8, and 9 will focus on first-class functions and function closures. By “first-class” we mean thatfunctions can be computed and passed wherever other values can in ML. As examples, we can pass themto functions, return them from functions, put them in pairs, have them be part of the data a datatypeconstructor carries, etc. Function closures refer to functions that use variables defined outside of them,which we will start seeing next lecture. The term higher-order function just refers to a function that takesor returns other functions.Taking functions as argumentsThe most common use of first-class functions is passing them as arguments to other functions, so we motivatethis use first.Here is a first example of a function that takes another function:fun n_times (f,n,x) =if n=0then xelse f (n_times(f,n-1,x))We can tell the argument f is a function because the last line calls f with an argument. What n_times doesis compute f(f(...(f(x)))) where the number of calls to f is n. That is a genuinely useful helper functionto have around. For example, here are 3 different uses of it:fun double x = x+xval x1 = n_times(double,4,7) (* answer: 112 *)fun increment x = x+1val x2 = n_times(increment,4,7) (* answer: 11 *)val x3 = n_times(tl,2,[4,8,12,16]) (* answer: [12,16] *)Like any helper function, n_times lets us abstract the common parts of multiple computations so we canreuse some code in different ways by passing in different arguments. The main novelty is making one ofthose arguments a function, which is a powerful and flexible programming idiom. It also makes perfect sense— we are not introducing any new language constructs here, just using ones we already know in ways youmay not have thought of.Once we define such abstractions, we can find additional uses for them. For example, even if our programtoday does not need to triple any values n times, maybe tomorrow it will, in which case we can just definethe function triple_n_times using n_times:fun triple x = 3*xfun triple_n_times (n,x) = n_times(triple,n,x)Polymorphic Types1Let us now consider the type of n_times, which is (’a -> ’a) * int * ’a -> ’a. It might be simpler atfirst to consider the type (int -> int) * int * int -> int, which is how n_times is used for x1 and x2above: It takes 3 arguments, the first of which is itself a function that takes and returns an int. Similarly, forx3 we use n_times as though it has type (int list -> int list) * int * int list -> int list. Butchoosing either one of these types for n_times would make it less useful because only some of our exampleuses would type-check. The type (’a -> ’a) * int * ’a -> ’a says the third argument and result can beany type, but they have to be the same type, as does the argument and return type for the first argument.When types can be any type and do not have to be the same as other types, we use different letters (’b, ’c,etc.)This is called parametric polymorphism, or perhaps more commonly generic types. It lets functions takearguments of any type. It is technically a separate issue from first-class functions: there are functions thattake functions and do not have polymorphic types and there are functions with polymorphic types that donot take functions. However, many of our examples with first-class functions will have polymorphic types.That is a good thing because it makes our code more reusable.It is quite essential to ML. For example, without parametric polymorphism, we would have to redefine listsfor every type of element that a list might have. Instead, we can have functions that work for any kindof list, like length, which has type ’a list -> int even though it does not use any function arguments.Conversely, here is a higher-order function that is not polymorphic: it has type (int->int) * int -> int:1fun times_until_zero (f,x) =if x = 0 then 0 else 1 + times_until_zero(f, f x)Anonymous functionsThere is no reason that a function like triple that is passed to another function like n_times needs to bedefined at top-level. As usual, it is better style to define such functions locally if they are needed only locally.So we could write:fun triple_n_times (n,x) =let fun triple x = 3*x in n_times(triple,n,x) endIn fact, we could give the triple function an even smaller scope: we need it only as the first argument ton_times, so we could have a let-expression there that evaluates to the triple function:fun triple_n_times3 (n,x) = n_times((let fun triple y = 3*y in triple end), n, x)Notice that in this example, which is actually poor style, we need to have the let-expression “return” triplesince, as always, a let-expression produces the result of the expression between in and end. In this case, wesimply look up triple in the environment, and the resulting function is the value that we then pass as thefirst argument to n_times.ML has a much more concise way to define functions right where you use them, as in this final, best version:fun triple_n_times3 (n,x) = n_times((fn y => 3*y), n, x)This code defines an anonymous function fn y => 3*y. It is a function that takes an argument y and hasbody 3*y. The fn is a keyword and => (not =) is also part of the syntax. We never gave the function a name(it’s anonymous, see?), which is convenient because we did not need one. We just wanted to pass a functionto n_times, and in the body of n_times, this function is bound to f.1It would be better to make this function tail-recursive using an accumulator; see Lecture 6.2It is common to use anonymous functions as arguments to other functions. Moreover, you can put ananonymous function anywhere you can put an expression — it simply is a value, the function itself. Theonly thing you cannot do with an anonymous function is recursion, exactly because you have no name touse for the recursive call. In such cases, you need to use a fun binding as before, and fun bindings must bein let-expressions or at top-level.For non-recursive functions, you could use anonymous functions with val bindings instead of a fun binding.For example, these two bindings are exactly the same thing:fun increment x = x + 1val increment = fn x => x+1They both bind increment to a value that is a function


View Full Document

UW CSE 341 - Lecture Notes

Documents in this Course
Macros

Macros

6 pages

Macros

Macros

6 pages

Macros

Macros

3 pages

Mutation

Mutation

10 pages

Macros

Macros

17 pages

Racket

Racket

25 pages

Scheme

Scheme

9 pages

Macros

Macros

6 pages

Load more
Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?