cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
13 of 35
2/9/21, 8:58 AM
filter
The ¡°map¡± pattern
The map Pattern General Pattern
HOF map
Apply a transformation f to each element of a list
Specific Operations
Transformations toUpper and \x -> x * x
map f [] = []
map f (x:xs) = f x : map f xs
Lets refactor shout and squares
filter cond CT
L
x rest rest
filtercondCx I conax
I otherwise
where
filtercondxs I
rest
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
shout = map …
squares = map …
Q
map instances
QUIZ
What is the type of map ?
map f [] = []
map f (x:xs) = f x : map f xs
14 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
(A) (Char -> Char) -> [Char] -> [Char] (B) (Int -> Int) -> [Int] -> [Int]
(C) (a -> a) -> [a] -> [a]
(D) (a -> b) -> [a] -> [b]
(E) (a -> b) -> [c] -> [d]
— For any types `a` and `b`
— if you give me a transformation from `a` to `b`
— and a list of `a`s,
— I’ll give you back a list of `b`s map :: (a -> b) -> [a] -> [b]
f
Type says it all!
The only meaningful thing a function of this type can do is apply its first argument to elements of the list
Hoogle it!
is
15 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Things to try at home: 7
can you write a function map’ :: (a -> b) -> [a] -> [b] whose
behavior is di”erent from map ?
can you write a function map’ :: (a -> b) -> [a] -> [b] such that
map’ f xs returns a list whose elements are not in map f xs ?
z
X
QUIZ
x
x
What is the value of quiz ?
map :: (a -> b) -> [a] -> [b]
aint
quiz = map (\(x, y) -> x + y) [1, 2, 3]
(A) [2, 4, 6]
(B) [3, 5]
(C) Syntax Error
(D) Type Error
(E) None of the above
Int Int
16 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Don¡¯t Repeat Yourself
Benefits of factoring code with HOFs: Reuse iteration pattern
think in terms of standard patterns
lesstowrite1lesscodetofix maintain easier to communicate
Avoid bugs due to repetition
17 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Recall: length of a list
— len [] ==> 0
— len [“carne”,”asada”] ==> 2 len :: [a] -> Int
len [] =0
len (x:xs) = 1 + len xs
Recall: summing a list
— sum [] ==> 0 — sum [1,2,3] ==> 6 sum :: [Int] -> Int sum [] =0
sum (x:xs) = x + sum xs
18 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Example: string concatenation
Let¡¯s write a function cat :
— cat [] ==> “”
— cat [“carne”,”asada”,”torta”] ==> “carneasadatorta” cat :: [String] -> String
cat [] = …
cat (x:xs) = …
Can you spot the pattern?
19 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
— len
foo [] = 0
foo (x:xs) = 1 + foo xs
— sum
foo [] = 0
foo (x:xs) = x + foo xs
— cat
foo [] = “”
foo (x:xs) = x ++ foo xs
pattern = …
The ¡°fold-right¡± pattern
20 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
The foldr Pattern General Pattern
Recurse on tail
Combine result with the head using some binary operation
foldr f b [] = b
foldr f b (x:xs) = f x (foldr f b xs)
Let¡¯s refactor sum , len and cat : sum = foldr … …
cat = foldr … …
len = foldr … …
Factor the recursion out!
21 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
foldr instances
You can write it more clearly as
sum = foldr (+) 0
cat = foldr (++) “”
Nc
b
Nz Nz 2cgw
The ¡°fold-right¡± pattern
22 of 35 2/9/21, 8:58 AM
cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
23 of 35
2/9/21, 8:58 AM
foldr f b [a1, a2, a3, a4]
==> f a1 (foldr f b [a2, a3, a4])
==> f a1 (f a2 (foldr f b [a3, a4]))
==> f a1 (f a2 (f a3 (foldr f b [a4])))
==> f a1 (f a2 (f a3 (f a4 (foldr f b []))))
==> f a1 (f a2 (f a3 (f a4 b)))
cars
cat
cat deg
x IfI x
Accumulate the values from the right
For example:
dog
horse horse t
foldr (+) 0 [1, 2, 3, 4]
==> 1 + (foldr (+) 0 [2, 3, 4])
==> 1 + (2 + (foldr (+) 0 [3, 4]))
==> 1 + (2 + (3 + (foldr (+) 0 [4])))
==> 1 + (2 + (3 + (4 + (foldr (+) 0 []))))
==> 1 + (2 + (3 + (4 + 0)))
se
QUIZ
What does this evaluate to?
Kz
Nz
C
t seaPby
ok
op
z op 2cgop b
Tor
op
1
2cg
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
foldr f b [] =b
foldr f b (x:xs) = f x (foldr f b xs)
quiz = foldr (\x v -> x : v) [] [1,2,3]
(A) Type error
(B) [1,2,3]
(C) [3,2,1]
(D) [[3],[2],[1]] (E) [[1],[2],[3]]
X Kz Ks Ky
a C
x i K2 Nz
2cg
foldr (:) [] [1,2,3]
==> (:) 1 (foldr (:) [] [2, 3])
==> (:) 1 ((:) 2 (foldr (:) [] [3]))
==> (:) 1 ((:) 2 ((:) 3 (foldr (:) [] []))) ==> (:) 1 ((:) 2 ((:) 3 []))
== 1:(2:(3:[]))
== [1,2,3]
24 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
QUIZ
HW EXERUSE What is the most general type of foldr ?
foldr :: (a -> b -> b) -> b -> [a] -> b foldr f b [] =b
foldr f b (x:xs) = f x (foldr f b xs)
(A) (a -> a -> a) -> a -> [a] -> a (B) (a -> a -> b) -> a -> [a] -> b (C) (a -> b -> a) -> b -> [a] -> b (D) (a -> b -> b) -> b -> [a] -> b (E) (b -> a -> b) -> b -> [a] -> b
25 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Tail Recursive Fold
foldr f b [] = b
foldr f b (x:xs) = f x (foldr f b xs)
Is foldr tail recursive?
Not
TR
What about tail-recursive versions?
Let¡¯s write tail-recursive sum !
sumTR :: [Int] -> Int
sumTR = …
26 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Lets run sumTR to see how it works
sumTR [1,2,3]
==> helper 0 [1,2,3]
==> helper 1 [2,3]
==> helper 3 [3]
==> helper 6 []
==> 6
— 0 + 1 ==> 1
— 1 + 2 ==> 3
— 3 + 3 ==> 6
Note: helper directly returns the result of recursive call!
Let¡¯s write tail-recursive cat !
catTR :: [String] -> String
catTR = …
27 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Lets run catTR to see how it works
catTR
==> helper “”
==> helper “carne”
==> helper “carneasada”
==> helper “carneasadatorta”
[“carne”, “asada”, “torta”]
[“carne”, “asada”, “torta”]
[“asada”, “torta”]
[“torta”]
[]
==> “carneasadatorta”
Note: helper directly returns the result of recursive call!
28 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Can you spot the pattern?
— sumTR
foo xs = helper 0 xs
where
helper acc [] = acc
helper acc (x:xs) = helper (acc + x) xs
— catTR
foo xs = helper “” xs
where
helper acc [] = acc
helper acc (x:xs) = helper (acc ++ x) xs
pattern = …
The ¡°fold-left¡± pattern
29 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
The foldl Pattern General Pattern
Use a helper function with an extra accumulator argument
To compute new accumulator, combine current accumulator with the head using some binary operation
foldl f b xs = helper b xs
where
helper acc [] = acc
helper acc (x:xs) = helper (f acc x) xs
Let¡¯s refactor sumTR and catTR : sumTR = foldl … …
catTR = foldl … …
Factor the tail-recursion out!
30 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
QUIZ
What does this evaluate to?
foldl f b xs = helper b xs
where
helper acc [] = acc
helper acc (x:xs) = helper (f acc x) xs
quiz = foldl (\xs x -> x : xs) [] [1,2,3]
(A) Type error
(B) [1,2,3]
(C) [3,2,1]
(D) [[3],[2],[1]] (E) [[1],[2],[3]]
31 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
foldl f b (x1: x2: x3 : [])
==> helper b (x1: x2: x3 : [])
==> helper (f x1 b) (x2: x3 : [])
==> helper (f x2 (f x1 b)) (x3 : [])
==> helper (f x3 (f x2 (f x1 b))) []
==> ( x3 : (x2 : (x1 : [])))
The ¡°fold-left¡± pattern
foldl f b
==> helper b
==> helper (f b x1)
==> helper (f (f b x1) x2)
==> helper (f (f (f b x1) x2) x3) [x4]
==> helper (f (f (f (f b x1) x2) x3) x4) []
==> (f (f (f (f b x1) x2) x3) x4)
Accumulate the values from the left For example:
[x1, x2, x3, x4]
[x1, x2, x3, x4]
[x2, x3, x4]
[x3, x4]
32 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
foldl (+) 0
==> helper 0
==> helper (0 + 1)
==> helper ((0 + 1) + 2)
==> helper (((0 + 1) + 2) + 3)
==> helper ((((0 + 1) + 2) + 3) + 4) []
==> ((((0 + 1) + 2) + 3) + 4)
Left vs.Right
foldl f b [x1, x2, x3]
foldr f b [x1, x2, x3]
For example:
foldl (+) 0 [1, 2, 3]
foldr (+) 0 [1, 2, 3]
Di”erent types!
==> f (f (f b x1) x2) x3
==> f x1 (f x2 (f x3 b))
— Left
— Right
[1, 2, 3, 4]
[1, 2, 3, 4]
[2, 3, 4]
[3, 4]
[4]
==> ((0 + 1) + 2) + 3 — Left ==> 1 + (2 + (3 + 0)) — Right
33 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
foldl :: (b -> a -> b) -> b -> [a] -> b — Left foldr :: (a -> b -> b) -> b -> [a] -> b — Right
Higher Order Functions
Iteration patterns over collections:
Filter values in a collection given a predicate
Map (iterate) a given transformation over a collection
Fold (reduce) a collection into a value, given a binary operation to combine results
HOFs can be put into libraries to enable modularity
Data structure library implements map , filter , fold for its collections
generic e!cient implementation
generic optimizations: map f (map g xs) –> map (f.g) xs Data structure clients use HOFs with specific operations
no need to know the implementation of the collection
34 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Crucial foundation of
¡°big data¡± revolution e.g. MapReduce, Spark, TensorFlow ¡°web programming¡± revolution e.g. Jquery, Angular, React
(https://ucsd-cse130.github.io/wi21/feed.xml) (https://twitter.com/ranjitjhala) (https://plus.google.com/u/0/104385825850161331469) (https://github.com/ranjitjhala)
Generated by Hakyll (http://jaspervdj.be/hakyll), template by Armin Ronacher (http://lucumr.pocoo.org), suggest improvements here (https://github.com /ucsd-progsys/liquidhaskell-blog/).
35 of 35 2/9/21, 8:58 AM