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,
Ill 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 dierent 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
Dont 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
Lets 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)
Lets 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?
Lets 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!
Lets 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
Lets 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]
Dierent 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
Reviews
There are no reviews yet.