OutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsCS421 Lecture 4: Higher Order Functions1Mark [email protected] of Illinois at Urbana-ChampaignJune 5, 20061Based on slides by Mattox Beckman, as updated by Vikram Adve, GulAgha, and Elsa GunterMark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsMark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsObjectivesHigher Order Functions (HOFs) are fundamental to the design anduse of functional languages. Later, we will s tudy the LambdaCalculus, which formalizes the idea of computing with functions.The purp ose of this lecture is to give you an introduction to thecreation and use of hi gher order functions.As a re sult of this lecture (plus MP2), you should. . .◮know how to create HOFs◮learn how to understand complex combinations of HOFs◮understand relationships between different types of HOFsMark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsFirst Class TypesA type is first cl ass if it can be◮Passed as an argument◮Assigned as a value◮Returned as a resultExamples:◮C: scalars, p ointers , structures◮C++: same as C, plus classes◮Scheme, LISP: s calars, lists (s-expressions), functions◮ML: same as Scheme, plus user defined data typesMark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsFirst Class Types – Key Point◮The kind of data that can be manipulated well in a languagelargely determines for which applications the language is wellsuited◮The ability to treat functions as data is one of the strengthsof applicative programming languagesMark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsA function i s higher-order if it takes a function as an argument orreturns one as a result1 # let compose f g = fun x -> f (g x);;2 val compose : (’a -> ’b) -> (’c -> ’a) -> ’c -> ’b = <fun>The type (’a -> ’b) -> (’c -> ’a) -> ’c -> ’b is a higherorder type be cause of◮(’a -> ’b) – the first argument is a function◮and (’c -> ’a) – the second argument is a function◮and ’c -> ’b – the function returns a functionMark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsWhat are the types of the following functions?1 # plus_two;;2 - : int -> int = <fun>Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsWhat are the types of the following functions?1 # plus_two;;2 - : int -> int = <fun>1 # compose plus_two plus_two;;Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsWhat are the types of the following functions?1 # plus_two;;2 - : int -> int = <fun>1 # compose plus_two plus_two;;1 - : int -> int = <fun>Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsWhat are the types of the following functions?1 # plus_two;;2 - : int -> int = <fun>1 # compose plus_two plus_two;;1 - : int -> int = <fun>1 # compose plus_two;;Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsWhat are the types of the following functions?1 # plus_two;;2 - : int -> int = <fun>1 # compose plus_two plus_two;;1 - : int -> int = <fun>1 # compose plus_two;;1 - : (’_a -> int) -> ’_a -> int = <fun>Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsWhat do the following functions do?1 # plus_two;;2 - : int -> int = <fun>Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsWhat do the following functions do?1 # plus_two;;2 - : int -> int = <fun>1 # compose plus_two plus_two;;2 - : int -> int = <fun>Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainHigher Order FunctionsWhat do the following functions do?1 # plus_two;;2 - : int -> int = <fun>1 # compose plus_two plus_two;;2 - : int -> int = <fun>1 # compose plus_two;;2 - : (’_a -> int) -> ’_a -> int = <fun>Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to HOFsCurryingPartial Application and Lambda LiftingCurrying AgainThriceRecall our defi nition:1 # let thrice f x = f (f (f x));;2 val thrice : (’a -> ’a) -> ’a -> ’a = <fun>Mark Hills CS421 Lecture 4: Higher Order FunctionsOutlineFirst Class ValuesHigher Order FunctionsReverse, Folds, and MapsMiscellaneous HOFsSample ProblemsIntroduction to
View Full Document