DOC PREVIEW
U of I CS 421 - Higher Order Function

This preview shows page 1-2-3-4 out of 11 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 11 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 11 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 11 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 11 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 11 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

U of I CS 421 - Higher Order Function

Documents in this Course
Lecture 2

Lecture 2

12 pages

Exams

Exams

20 pages

Lecture

Lecture

32 pages

Lecture

Lecture

21 pages

Lecture

Lecture

15 pages

Lecture

Lecture

4 pages

Lecture

Lecture

68 pages

Lecture

Lecture

68 pages

Lecture

Lecture

84 pages

s

s

32 pages

Parsing

Parsing

52 pages

Lecture 2

Lecture 2

45 pages

Midterm

Midterm

13 pages

LECTURE

LECTURE

10 pages

Lecture

Lecture

5 pages

Lecture

Lecture

39 pages

Load more
Download Higher Order Function
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 Higher Order Function 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 Higher Order Function 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?