COMP0020: Functional Programming Higher Order Functions
COMP0020 Functional Programming Lecture 10
Higher Order Functions (2)
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 1 / 20
COMP0020: Functional Programming Higher Order Functions
Contents
Discussion of solutions to “challenge”
Capturing common forms of recursion on lists
The Miranda functions foldr and foldl ⋆ (reduce and accumulate)
Examples : summing a list of numbers Combining HOFs
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 2 / 20
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 :
The number of 1s before the first 0
The number of 2s before the first 0
The length of the longest sequence of 1s before the first 0
Notes :
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.
Start by writing down the type of the function (always !)
Be prepared to write small “helper” functions, or look in the online manual (Section 28) for built-in
operators.
If you find this easy, try designing the program a different 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 2019-2020 3 / 20
COMP0020: Functional Programming Higher Order Functions
Solution 1
challenge :: [num] − > (num, num, num)
challenge any = xchallenge any
xchallenge (0 : xs) (a, b, c, d) xchallenge (1:xs) (a,b,c,d) xchallenge (2 : xs) (a, b, c, d) xchallenge any (a, b, c, d)
(0, 0, 0, 0)
= (a, b, max [c, d])
= xchallengexs(a+1,b,c,d+1)
= xchallenge xs (a, b + 1, max [c, d], 0) = error “bad input format”
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 4 / 20
COMP0020: Functional Programming Higher Order Functions
Solution 2
challengeany =(a,b,c) where
f []
f (2 : xs) longest f (1 : xs) longest f any longest
segment = takewhile (∼= 0) any a = # (filter (= 1) segment)
b = # (filter (= 2) segment)
c =f segment00
current = max [longest, current]
current = f xs (max [current, longest]) 0 current = f xs longest (current + 1) current = error “bad input format”
longest
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
5 / 20
COMP0020: Functional Programming Higher Order Functions
Solution 3
challengeany =(a,b,c) where
segment a
b
c
g 1 (a, b)
g 2 (a, b)
g x (a,b) mymax (a, b)
= takewhile (∼= 0) any
= # (filter (= 1) segment )
= # (filter (= 2) segment )
= mymax (foldr g (0, 0) segment ) = (a, b + 1)
= (max [a,b], 0)
= error “bad input format”
= a, if a > b
= b, otherwise
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
6 / 20
COMP0020: Functional Programming Higher Order Functions
Foldr (sometimes known as “reduce”)
Distributes a dyadic function over the elements of a list foldr ( +) 0 anylist
↑ ↑ replaces “nil” in anylist ↑ replaces “cons” in anylist
Exampl e :
foldr (+) 0 (1: (2 : (3: [])))
→ (1 + (2 + (3 + 0 ))) →6
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 7 / 20
COMP0020: Functional Programming Higher Order Functions
Foldl (sometimes known as “accumulate”)
Distributes a dyadic function over the elements of a list; associates to the LEFT foldl (+) 0 anylist
↑ ↑ replaces “nil” in anylist (moved to LEFT end) ↑ replaces “cons” in anylist
Exampl e :
foldl (+) 0 (1:(2:(3:[])))
→ (((0 + 1) + 2) + 3 ) →6
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 8 / 20
COMP0020: Functional Programming Higher Order Functions
Definition of foldr
foldr ::(∗−>∗∗−>∗∗)−>∗∗−>[∗]−>∗∗ foldr f def [] = def
foldrf def (x:xs) = f x(foldrf def xs)
Note “f” is used in PREFIX position
foldr(+)0 (1 : (2 : (3 : [])))
≡ foldr (+) 0 ((:) 1 ((:) 2 ((:) 3 [])))
→ ≡
((+) 1 ((+) 2 ((+) 3 0))) (1 + (2 + (3 + 0)))
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
9 / 20
COMP0020: Functional Programming Higher Order Functions
Definition of foldl
foldl ::(∗∗−>∗−>∗∗)−>∗∗−>[∗]−>∗∗ foldl f def [] = def
foldl f def (x :xs) = foldl f (f def x)xs
Note again “f” is used in PREFIX position
foldl(+)0 (1 : (2 : (3 : [])))
≡ foldl (+) 0 ((:) 1 ((:) 2 ((:) 3 [])))
→ ≡
((+) ((+) ((+) 0 1) 2) 3) (((0 + 1) + 2) + 3)
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
10 / 20
COMP0020: Functional Programming Higher Order Functions
Examples
foldr (*) 1 [1,2,3,4] → 24
foldl (+) 0 [1,2,3,4] → 10
foldr ( 🙂 [] [1,2,3,4] → [1,2,3,4]
main = foldr g 0 [1,2,3,4] where
g x y = x, if x > y = y, otherwise
→4
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
11 / 20
COMP0020: Functional Programming Higher Order Functions
“Solution 3″ revisited :
challengeany =(a,b,c) where
segment a
b
c
g 1 (a, b)
g 2 (a, b)
g x (a,b) mymax (a, b)
= takewhile ( = 0) any
= # (filter (= 1) segment )
= # (filter (= 2) segment )
= mymax (foldr g (0, 0) segment ) = (a, b + 1)
= (max [a,b], 0)
= error “bad input format”
= a, if a > b
= b, otherwise
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
12 / 20
COMP0020: Functional Programming Higher Order Functions
“Solution 3″ revisited :
g 1 (a, b) g 2 (a, b) g x (a, b)
mymax (foldr g (0,0) [1,2,1,1,1,2,])
→ mymax (g 1 (foldr g (0,0) [2,1,1,1,2,]))
→ mymax (g 1 (g 2 (foldr g (0,0) [1,1,1,2])))
→→ mymax (g 1(g 2(g 1(g 1(g 1(g 2(0,0))))))) → mymax (g 1(g 2(g 1(g 1(g 1(0,0))))))
→ mymax (g 1(g 2(g 1(g 1(0,1)))))
→ mymax (g 1(g 2(g 1(0,2))))
→ mymax (g 1 (g 2 (0,3)))
→ mymax(g1(3,0))
→ mymax (3,1)
→3
Christopher D. Clack (University College London) COMP0020: Functional Programming
= (a, b + 1)
= (max [a, b], 0)
= error “bad input format”
Academic Year 2019-2020
13 / 20
COMP0020: Functional Programming Higher Order Functions
Equivalence of foldr and foldl ?
Can foldr be replaced with foldl without changing the result ?
foldr (-) 0 [1,2,3]
foldl (-) 0 [1,2,3]
Never ?
Always ?
Sometimes? … if so, when?
Christopher D. Clack (University College London)
COMP0020: Functional Programming
Academic Year 2019-2020
14 / 20
COMP0020: Functional Programming Higher Order Functions
Equivalence of foldr and foldl
They CAN be interchanged whenever the function “f” is :
Associative, AND
Commutative with the “def” value (often the identity value of the function “f”)
Caveat – they don’t work the same on infinite lists !
hd(foldr(:)[]ones)→1
hd (foldl (swap ( :)) [] ones) → ?
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 15 / 20
COMP0020: Functional Programming Higher Order Functions
Combining HOFs
results = [(”fred”,45),(”sally”,79),(”chris”,65)]
f main
= (map fst) . (filter ((< 50).snd))
= f results
→ ((map fst) . (filter ((< 50).snd))) results
→ (map fst )
→ map fst
→ map fst
→ [”fred”]
((filter ((< 50).snd )) results )
(filter ((< 50).snd ) [(”fred ”, 45), (”sally ”, 79), (”chris ”, 65)]) [(”fred ”, 45)]
Christopher D. Clack (University College London)
COMP0020: Functional Programming Academic Year 2019-2020 16 / 20
COMP0020: Functional Programming Higher Order Functions
Combining HOFs
myreverse = foldl (swap (:)) []
main
= myreverse[1,2,3,4]
→ (foldl (swap (:)) []) [1, 2, 3, 4]
→ foldl (swap (:)) [] [1, 2, 3, 4]
→ foldl (swap (:)) (swap (:) [] 1) [2, 3, 4]
→ foldl (swap (:)) (swap (:) (swap (:) [] 1) 2) [3, 4]
→ foldl (swap (:)) (swap (:) (swap (:)(swap (:) [] 1) 2) 3) [4]
→ foldl (swap (:)) (swap (:) (swap (:) (swap (:)(swap (:) [] 1) 2) 3) 4) [] → (swap (:) (swap (:) (swap (:)(swap (:) [] 1) 2) 3) 4)
→ (:) 4 (swap (:) (swap (:)(swap (:) [] 1) 2) 3)
→→ (:)4((:)3((:)2((:)1[])
→→ (4 :(3 : (2 : (1 : [])))) ≡ [4,3,2,1]
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 17 / 20
COMP0020: Functional Programming Higher Order Functions
Combining HOFs
Don’t go overboard : things can get silly ! What does this do ?
g=(foldr(+)0).(foldr ((:).((#).(:[]))) [])
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 18 / 20
COMP0020: Functional Programming Higher Order Functions
Summary
Summary
Discussion of solutions to “challenge"
Capturing common forms of recursion on lists
The Miranda functions foldr and foldl ⋆ (reduce and accumulate)
Examples Combining HOFs
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 19 / 20
COMP0020: Functional Programming Higher Order Functions
Summary
END OF LECTURE
Christopher D. Clack (University College London) COMP0020: Functional Programming Academic Year 2019-2020 20 / 20