程序代写代做代考 COMP0020: Functional Programming

COMP0020: Functional Programming
Higher Order Functions
COMP0020 Functional Programming Lecture 9
Combinators and Higher Order Functions
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 7 / 45

COMP0020: Functional Programming
Higher Order Functions
Contents
Combinators
I Definition
I Examples : S, K, I
Higher Order Functions
I Definition
I Example : composition
Capturing common forms of recursion on lists
I Examples : map and filter
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 8 / 45

COMP0020: Functional Programming
Higher Order Functions
Combinators
Definition
I A combinator is a function that contains no free variables Examples :
fst (x,y) = x
idx =x
cancelxy =x
swapf xy =f yx distributef gx=f x(gx) ||“SÕÕ
||“I ÕÕ ||“K ÕÕ ||“CÕÕ
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 9 / 45

COMP0020: Functional Programming
Higher Order Functions
Combinators (2)
Basis for implementation
S & K computationally complete
All required data available via arguments (passed on the stack) so no need to search for distant bindings
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 10 / 45

COMP0020: Functional Programming
Higher Order Functions
Higher Order Functions
Definition :
I A Higher Order Function is a function that either (i) takes a function as an argument, or (ii) returns a function as a result, or (iii) both.
fgx =(gx)
h x = (+ x)
j f p g = (+ (f p)), if p
= (+ (g p)), otherwise
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 11 / 45

COMP0020: Functional Programming
Higher Order Functions
Higher Order Functions : types
f :: (ú ≠>úú)≠>ú≠>úú f g x = (g x)
h::num ≠>(num≠>num) h x = (+ x)
j ::(bool ≠>num)≠>bool ≠>(bool≠>num)≠>(num≠>num) j f p g = (+ (f p)), if p
= (+ (g p)), otherwise
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 12 / 45

COMP0020: Functional Programming
Higher Order Functions
Function composition
compose :: (úú≠>úúú)≠>(ú≠>úú)≠>ú≠>úúú compose f g x = f (g x)
Can partially apply “compose” :
Built-in operator “.”
fred = (compose (+1) abs) main = fred (≠3)
fred = ((+1) . abs)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 13 / 45

COMP0020: Functional Programming
Higher Order Functions
Function composition (2)
twice x = x * 2
many x = twice (twice (twice (twice x)))
mymany : : num -> num
mymany = (twice . twice . twice . twice)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 14 / 45

COMP0020: Functional Programming
Higher Order Functions
Example HOF
“myiterate” repeatedly applies its second parameter to its final parameter ; the final parameter is an accumulator for the result. The function loops n times, where n is the first parameter :
myiterate :: num ≠ > (ú≠ > ú)≠ > ú ≠ > ú myiterate 0 f state = state
myiterate n f state = myiterate (n ≠ 1) f (f state)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 15 / 45

COMP0020: Functional Programming
Higher Order Functions
Example HOF
printdots n = myiterate n ((++) ”.”) ””
printdots 3
æ myiterate 3 ((++) ”.”)
”” ((++) ”.” ””) ((++) ”.” ((++) ”.” ””) ((++) ”.”((++) ”.” ((++) ”.” ””)))
æ myiterate
æ myiterate
æ myiterate
æ ((++) ”.” ((++) ”.” ((++) ”.” ””))) æ ”…”
2 ((++) ”.”) 1 ((++) ”.”) 0 ((++) ”.”)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 16 / 45

COMP0020: Functional Programming
Higher Order Functions
Recursion on lists : capturing common forms
Mapping a function across the values of a list :
notlist [] = []
notlist (x : xs) = ((≥ x) : (notlist xs))
inclist [] = []
inclist (x : xs) = ((x + 1) : (inclist xs))
abslist [] = []
abslist (x : xs) = ((abs x) : (abslist xs))
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 17 / 45

COMP0020: Functional Programming
Higher Order Functions
Recursion on lists : map
Built-in function “map” makes life easier :
Or, simply :
notlist any = map (≥) any inclist any = map (+1) any
abslist any = map abs any
notlist = map (≥) inclist = map (+1)
abslist = map abs
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 18 / 45

COMP0020: Functional Programming
Higher Order Functions
Definition of map
map f [] = []
mapf (x:xs)= ((f x):(mapf xs))
So, what is the type of map ?
Write it here (don’t “cheat” yourself by asking Miranda — work it out for yourself !) :
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 19 / 45

COMP0020: Functional Programming
Higher Order Functions
Recursion on lists : capturing common forms
Filtering some elements out of a list :
firsts [] = []
firsts (x :xs) = (x :(firsts xs)), if (x >=70)
= firsts xs, otherwise
not34[] = []
not34(x :xs)= (x :(not34xs)), if (x ≥=34)
= not34 xs, otherwise
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 20 / 45

COMP0020: Functional Programming
Higher Order Functions
Recursion on lists : filter
Recursion on lists : filter
Or, simply :
firsts any = filter (>= 70) any not34 any = filter (≥= 34) any
firsts = filter (>= 70) not34 = filter (≥= 34)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 21 / 45

COMP0020: Functional Programming
Higher Order Functions
Definition of filter
filter p [] = []
filterp(x:xs)= (x : (filterpxs)),if (px)
= filter p xs, otherwise
So, what is the type of filter ?
Write it here (don’t “cheat” yourself by asking Miranda — work it out for yourself !) :
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 22 / 45

COMP0020: Functional Programming
Higher Order Functions
Challenge
Can you write a function that takes a list of numbers (containing only the values 1, 2 and 0, where at least one 0 must occur) and returns a three-tuple containing :
I The number of 1s before the first 0
I The number of 2s before the first 0
I The length of the longest sequence of 1s before the first 0
Notes :
I The value of this challenge is NOT in knowing the answer — the value is in the process of finding the answer ! So please don’t “cheat” yourself by searching for the answer or looking at somebody else’s answer.
I Start by writing down the type of the function (always !)
I Be prepared to write small “helper” functions, or look in the online manual (Section 28) for built-in
operators.
I If you find this easy, try designing the program a dierent way so that it makes use of higher order
functions (e.g. filter, dropwhile, takewhile)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 23 / 45

COMP0020: Functional Programming
Higher Order Functions
Summary
Summary
Combinators
I Definition
I Example : S, K, I
Higher Order Functions
I Definition
I Example : composition
Use of example HOF
Capturing common forms of recursion on lists
I Examples : map and filter
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 24 / 45

COMP0020: Functional Programming
Higher Order Functions
Summary
END OF LECTURE
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2018-2019 25 / 45

Related Posts