cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Higher-Order Functions Plan for this week
Last week:
user-defined data types
manipulating data-types with pattern matching and recursion how to make recursive functions more e!cient with tail recursion
The long arc of history
Pattern matching is a very old PL idea …
Variants of LISP from 1970 by Fred McBride (https://personal.cis.strath.ac.uk
/conor.mcbride/FVMcB-PhD.pdf) … but will finally be added to Python 3.10
https://www.python.org/dev/peps/pep-0622/
1 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
def make_point_3d(pt): match pt:
case (x, y):
return Point3d(x, y, 0)
case (x, y, z):
return Point3d(x, y, z)
case Point2d(x, y):
return Point3d(x, y, 0)
case Point3d(_, _, _):
return pt
case _:
raise TypeError(“not a point we support”)
Plan for this week
Last week:
user-defined data types
manipulating data-types with pattern matching and recursion how to make recursive functions more e!cient with tail recursion
This week:
2 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
code reuse with higher-order functions (HOFs) some useful HOFs: map , filter , and fold
Recursion is good…
Recursive code mirrors recursive data
Base constructor -> Base case
Inductive constructor -> Inductive case (with recursive call)
But it can get kinda repetitive!
Example: evens
3 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Let¡¯s write a function evens : — evens [] ==> []
— evens [1,2,3,4] ==> [2,4]
I
1
evens
evens []
evens (x:xs) = …
:: [Int] -> [Int]
= …
Example: four-letter words
Let¡¯s write a function fourChars : — fourChars [] ==> []
— fourChars [“i”,”must”,”do”,”work”] ==> [“must”,”work”]
fourChars :: [String] -> [String]
fourChars [] = …
fourChars (x:xs) = …
F
4 of 35 boy
raff
2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Yikes! Most Code is the Same!
Lets rename the functions to foo :
foo []
foo (x:xs)
= []
= x : foo xs
foo xs
foo [] = []
foo (x:xs)
| length x == 4 = x : foo xs
| otherwise = foo xs
Only di”erence is condition
x mod 2 == 0 vs length x == 4
|xmod2==0
| otherwise =
Moral of the day
5 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
D.R.Y. Don¡¯t Repeat Yourself!
Can we
reuse the general pattern and plug-in the custom condition?
is
filter d
is 4
1
Higher-Order Functions
General Pattern
expressed as a higher-order function
takes plugin operations as arguments Specific Operation
passed in as an argument to the HOF
Even
6 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
The ¡°filter¡± pattern
II
The filter Pattern General Pattern
HOF filter
Recursively traverse list and pick out elements that satisfy a predicate
Specific Operations
Predicates isEven and isFour
as as as as
filter instances Avoid duplicating code!
7 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
QUIZ: What is the type of filter?
— evens [1,2,3,4] ==> [2,4]
evens :: [Int] -> [Int]
evens xs = filter isEven xs
where
isEven :: Int -> Bool
isEven x = x `mod` 2 == 0
— fourChars [“i”,”must”,”do”,”work”] ==> [“must”,”work”]
fourChars :: [String] -> [String]
fourChars xs = filter isFour xs
where
isFour :: String -> Bool
isFour x = length x == 4
So what¡¯s the type of filter ?
8 of 35 2/9/21, 8:58 AM
cse130
file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
9 of 35
2/9/21, 8:58 AM
{- A -} filter :: (Int -> Bool) -> [Int] -> [Int]
{- B -} filter :: (String -> Bool) -> [String] -> [String]
{- E -} filter :: (a -> b) -> [a] -> [b]
collectionof a
{- C -} filter :: (a -> Bool) -> [a] -> [a] thesub list
Gund checks if a TRUET that {- D -} filter :: (a -> Bool) -> [a] -> [Bool]
Type of filter
FALSE satify cord
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
— evens [1,2,3,4] ==> [2,4]
evens :: [Int] -> [Int]
evens xs = filter isEven xs
where
isEven :: Int -> Bool
isEven x = x `mod` 2 == 0
— fourChars [“i”,”must”,”do”,”work”] ==> [“must”,”work”]
fourChars :: [String] -> [String]
fourChars xs = filter isFour xs
where
isFour :: String -> Bool
isFour x = length x == 4
For any type a
Input a predicate a -> Bool and collection [a]
Output a (smaller) collection [a]
filter does not care what the list elements are Tay
as long as the predicate can handle them
filter is polymorOphic (generic) in the type of list elements
nt Bool
filter :: (a -> Bool) -> [a] -> [a]
stray
10 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
Example: ALL CAPS!
Lets write a function shout :
— shout [] ==> []
— shout [‘h’,’e’,’l’,’l’,’o’] ==> [‘H’,’E’,’L’,’L’,’O’]
shout :: [Char] -> [Char]
shout [] = …
shout (x:xs) = …
Example: squares
Lets write a function squares :
— squares [] ==> []
— squares [1,2,3,4] ==> [1,4,9,16]
11 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
squares :: [Int] -> [Int]
squares [] = …
squares (x:xs) = …
Yikes, Most Code is the Same
Lets rename the functions to foo :
— shout
foo [] =[]
foo (x:xs) = toUpper x : foo xs
— squares
foo [] =[]
foo (x:xs) = (x * x) : foo xs
Lets refactor into the common pattern pattern = …
12 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
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
13 of 35 2/9/21, 8:58 AM
cse130 file:///Users/rjhala/teaching/130-wi21/docs/lectures/04-hof.html
shout =map… squares = map …
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
Don¡¯t Repeat Yourself
Benefits of factoring code with HOFs: Reuse iteration pattern
think in terms of standard patterns less to write
easier to communicate
Avoid bugs due to repetition
17 of 35 2/9/21, 8:58 AM