Slide 1On to first-class functionsFirst-class functionsExampleTypesPolymorphism and higher-order functionsToward anonymous functionsAnonymous functionsUsing anonymous functionsA style pointMapFilterReturning functionsOther data structuresCSE341: Programming LanguagesLecture 7Functions Taking/Returning FunctionsDan GrossmanFall 2011On to first-class functions“Functional programming” can mean a few different things:1. Avoiding mutation in most/all cases (done and ongoing)2. Using functions as values (the next week)… Recursion? Mathematical definitions? Not OO? Laziness (later)?Fall 2011 2CSE341: Programming LanguagesFirst-class functions•Functions are (first-class) values: Can use them wherever we use values–Arguments, results, parts of tuples, bound to variables, carried by datatype constructors or exceptions, …•Most common use is as an argument / result of another function–The other function is called a higher-order function–Powerful way to factor out common functionality•3-ish lectures on how and why to use first-class functionsFall 2011 3CSE341: Programming LanguagesExampleCan reuse n_times rather than defining many similar functions–Computes f(f(…f(x))) where number of calls is nFall 2011 4CSE341: Programming Languagesfun n_times (f,n,x) = if n=0 then x else f (n_times(f,n-1,x))fun double x = x + xfun increment x = x + 1val x1 = n_times(double,4,7)val x2 = n_times(increment,4,7)val x3 = n_times(tl,2,[4,8,12,16,20])fun double_n_times (n,x) = n_times(double,n,x)fun nth_tail (n,x) = n_times(tl,n,x)Types•val n_times : ('a -> 'a) * int * 'a -> 'a•Two of our examples instantiated 'a with int•One of our examples instantiated 'a with int list•This polymorphism makes n_times more useful•Type is inferred based on how arguments are used (later lecture) –Describes which types must be exactly something (e.g., int) and which can be anything but the same (e.g., 'a)Fall 2011 5CSE341: Programming LanguagesPolymorphism and higher-order functions•Many higher-order functions are polymorphic because they are so reusable that some types, “can be anything”•But some polymorphic functions are not higher-order–Example: length : 'a list -> int•And some higher-order functions are not polymorphic–Example: times_til_0 : (int -> int) * int -> intFall 2011 6CSE341: Programming Languagesfun times_til_0 (f,x) = if x=0 then 0 else 1 + times_til_0(f, f x)* Would be better with tail-recursionToward anonymous functions•Definitions unnecessarily at top-level are still poor style:Fall 2011 7CSE341: Programming Languages•So this is better (but not the best):•And this is even smaller scope–It makes sense but looks weird (poor style; see next slide)fun triple x = 3*xfun triple_n_times (f,x) = n_times(triple,n,x)fun triple_n_times (f,x) = let fun trip y = 3*y in n_times(trip,n,x) endfun triple_n_times (f,x) = n_times(let fun trip y = 3*y in trip end, n, x)Anonymous functions•This does not work: A function binding is not an expressionFall 2011 8CSE341: Programming Languages•This is the best way we were building up to: an expression form for anonymous functions–Like all expression forms, can appear anywhere –Syntax: •fn not fun•=> not =•no function name, just an argument patternfun triple_n_times (f,x) = n_times((fun trip y = 3*y), n, x)fun triple_n_times (f,x) = n_times((fn y => 3*y), n, x)Using anonymous functions•Most common use: Argument to a higher-order function–Don’t need a name just to pass a function•But: Cannot use an anonymous function for a recursive function–Because there is no name for making recursive calls–If not for recursion, fun bindings would be syntactic sugar for val bindings and anonymous functionsFall 2011 9CSE341: Programming Languagesfun triple x = 3*xval triple = fn y => 3*yA style pointCompare:With:So don’t do this:When you can do this:Fall 2011 10CSE341: Programming Languages n_times((fn y => tl y),3,xs) n_times(tl,3,xs) if x then true else false (fn x => f x)MapMap is, without doubt, in the higher-order function hall-of-fame–The name is standard (for any data structure)–You use it all the time once you know it: saves a little space, but more importantly, communicates what you are doing–Similar predefined function: List.map•But it uses currying (lecture 9)Fall 2011 11CSE341: Programming Languagesfun map (f,xs) = case xs of [] => [] | x::xs’ => (f x)::(map(f,xs’))map : ('a -> 'b) * 'a list -> 'b listFilterFilter is also in the hall-of-fame–So use it whenever your computation is a filter–Similar predefined function: List.filter•But it uses currying (lecture 9)Fall 2011 12CSE341: Programming Languagesfun filter (f,xs) = case xs of [] => [] | x::xs => if f x then x::(filter(f,rest)) else filter(f,rest)filter : ('a -> bool) * 'a list -> 'a listReturning functions•Remember: Functions are first-class values–For example, can return them from functions•Silly example: Has type (int -> bool) -> (int -> int) But the REPL prints (int -> bool) -> int -> int because it never prints unnecessary parentheses and t1 -> t2 -> t3 -> t4 means t1->(t2->(t3->t4))Fall 2011 13CSE341: Programming Languagesfun double_or_triple f = if f 7 then fn x => 2*x else fn x => 3*xOther data structures•Higher-order functions are not just for numbers and lists•They work great for common recursive traversals over your own data structures (datatype bindings) too–Example of a higher-order predicate: Are all constants in an arithmetic expression even numbers?Use a more general function of type (int -> bool) * exp -> boolAnd call it with (fn x => x mod 2 = 0)Fall 2011 14CSE341: Programming
View Full Document
Unlocking...