H. Conrad Cunningham
2 October 2018
Copyright (C) 2017, 2018, H. Conrad Cunningham
Acknowledgements: I originally created these slides in Fall 2017 to accompany what is now Chapter 15, Higher Order Functions, in the 2018 version of the textbook Exploring Languages with Interpreters and Functional Programming.
Browser Advisory: The HTML version of this document may require use of a browser that supports the display of MathML. A good choice as of October 2018 is a recent version of Firefox from Mozilla.
Demonstrate how to “think like a functional programmer”
Introduce concepts of first-class and higher-order functions
Illustrate how to generalize computational patterns
Develop useful library of higher-order list functions (map
, filter
, foldr
, foldl
, concatMap
,
etc)
Reinforce correct, efficient, and elegant function designs
To perform same computation on similar data structures
encapsulate computation in first-order polymorphic function
pass data structure as argument
example: length :: [a] -> Int
To perform similar computations on similar data structures
encapsulate computation in higher-order polymorphic function
also pass function for subcomputation as argument
example: same function can either add or multiply all elements of list
can be stored in a data structure, passed as argument, returned as result
takes functions as arguments or returns function as result
Haskell functions are first class values, can be higher-order
Haskell higher-order functions (HOF)
$\Longrightarrow$ construct powerful abstractions and operations
$\Longrightarrow$ express concise, “easy-to-understand” programs
$\Longrightarrow$ “glue together” programs from library functions and new program fragments
$\Longrightarrow$ improve programmer productivity and program reliability
map
) squareAll :: [Int] -> [Int]
squareAll [] = []
squareAll (x:xs) = (x * x) : squareAll xs
lengthAll :: [[a]] -> [Int]
lengthAll [] = []
lengthAll (xs:xss) = (length xs) : lengthAll xss
Take different kinds of data
Apply different operations
But both take list, apply function to each element, generate new list with same order and length
map
Generalizes squareAll
,
lengthAll
, and similar
functions
Adds higher-order parameter f
for operation applied
Makes input and output lists polymorphic of different types
map
squareAll2 :: [Int] -> [Int]
squareAll2 xs = map' sq xs
where sq x = x * x
lengthAll2 :: [[a]] -> [Int]
lengthAll2 xss = map' length xss
sq
and length
one-argument functions
What are map
’s types
a
and b
in above?
map
Under what circumstances does map' f xs
terminate normally?
(What preconditions?)
What is time complexity of map f xs
?
What is space complexity of map f xs
?
squareAll2 :: [Int] -> [Int]
squareAll2 xs = map' sq xs
where sq x = x * x
lengthAll2 :: [[a]] -> [Int]
lengthAll2 xss = map' length xss
What is time complexity of squareAll2 xs
? space
complexity?
What is time complexity of lengthAll2 xs
? space
complexity?
map
is recursive list function, but can consider it:
powerful list operator transforming elements simultaneously
Parallelism “easy” given referential transparency & immutable
data—consider Google’s mapReduce
operator node in dataflow network
Demand-driven network enabled by lazy evaluation stream
$\longrightarrow$
[map
node]
$\longrightarrow$
transformed-stream
Do scope-commonality-variability analysis (SCV) on set of functions
scope: what is and is not included
commonalities: parts of functions that are same (frozen spots)
variabilities: parts of functions that differ (hot spots)
Leave commonalities in function body.
Move variabilities into type signature & parameter list
Move variabilities into type signature & parameter list
Make expression moved a function with parameter for each local variable accessed
Add type parameter to signature for types that differ among functions in scope
Add distinct type or value parameter for each potential role that type/value plays among functions in scope
Consider other approaches if many new parameters (e.g., new procedural or data abstractions)
filter
)Study similar functions
Take integer list and return integer list
For empty input, return empty output
Maintain relative order from input and output
Select some elements to copy; others not to copy
What is type of input and output list elements (Int
type
arbitrary)
How to select value (getEven
uses even
, doublePos
compares with 0)
How to transform selected value (doublePos
doubles, getEven
leaves unchanged)
filter
filter' :: (a -> Bool) -> [a] -> [a] -- filter in Prelude
filter' _ [] = []
filter' p (x:xs)
| p x = x : xs'
| otherwise = xs'
where xs' = filter' p xs
Takes and returns list of type [a]
Takes predicate function p
of type a -> Bool
Returns list containing elements that satisfy p
in same order
But does not implement transformation operation
filter
getEven2 :: [Int] -> [Int]
getEven2 xs = filter' even xs
doublePos2 :: [Int] -> [Int]
doublePos2 xs = map' dbl (filter' pos xs)
where dbl x = 2 * x
pos x = (0 < x)
Reuse map
to
transform data in doublePos
Restate three-leg definition of getEven
/doublePos
in one leg
Except simple local definitions in doublePos
, which we eliminate
later
filter
filter' :: (a -> Bool) -> [a] -> [a] -- filter in Prelude
filter' _ [] = []
filter' p (x:xs)
| p x = x : xs'
| otherwise = xs'
where xs' = filter' p xs
Under what circumstances does filter' p xs
terminate normally?
(What preconditions?)
What is time complexity of filter' p xs
?
What is space complexity of filter' p xs
?
getEven2 :: [Int] -> [Int]
getEven2 xs = filter' even xs
doublePos2 :: [Int] -> [Int]
doublePos2 xs = map' dbl (filter' pos xs)
where dbl x = 2 * x
pos x = (0 < x)
What is the time complexity of getEven2 xs
? space
complexity?
What is the time complexity of doublePos2 xs
? space
complexity?
foldr
)Study similar functions
Take list
Insert binary operator between consecutive list elements (associative for these)
Reduce list to single return value
Group operations right to left
Return some value for nil list (as “rightmost” value of nonempty)
Here value is (right) identity of operation
Differ in element type (Int
, Integer
, [a]
)
Differ in operation inserted (addition, multiplication, list append)
Differ in value returned for nil input list—(right) identity
element (0, 1, []
)
Differ in return type (Int
, Integer
, a
)
Here each same as input element type, but can it differ?
Is associativity important? identity?
Do not assume
Observe operations of type a -> a -> a
Consider more general operations of type a -> b -> b
$\Longrightarrow$
return value of type b
for empty
or nonempty lists
foldr
(1) foldrX :: (a -> b -> b) -> b -> [a] -> b -- foldr in Prelude
foldrX f z [] = z
foldrX f z (x:xs) = f x (foldrX f z xs)
Separates input element type a
from output value type b
Takes general binary operation f
(of type a -> b -> b
)
to “fold” list
Takes “seed” value z
(of
type b
) as return for empty
lists
Does not depend upon operation being associative or having identity
foldr
(2) foldrX :: (a -> b -> b) -> b -> [a] -> b -- foldr
foldrX f z [] = z
foldrX f z (x:xs) = f x (foldrX f z xs)
foldr f z [1,2,3]
expands to
foldr
foldr
foldrX :: (a -> b -> b) -> b -> [a] -> b -- foldr
foldrX f z [] = z
foldrX f z (x:xs) = f x (foldrX f z xs)
Under what circumstances does foldrX f z xs
terminate normally?
(What preconditions?)
What is time complexity of foldrX f z xs
? space
complexity?
Backward recursive, so possible stack overflow for complex f
or long xs
product2 :: [Int] -> Int -- product
product2 xs = foldrX (*) 1 xs
concat2:: [[a]] -> [a] -- concat
concat2 xss = foldrX (++) [] xss
What is time complexity of product2 xs
? space
complexity?
What is time complexity of concat2 xs
? space complexity?
foldr
for map
map inc [1,2] = mf 1 (mf 2 [])
where inc x = x+1
Moving right to left folding function mf
applies map function f
to
next element
attaches result as head of processed tail
Uses nil list for seed—mf
has no identity but foldr
useful!
foldr
for filter
filter2 :: (a -> Bool) -> [a] -> [a] -- filter
filter2 p xs = foldr ff [] xs
where ff y ys = if p y then (y:ys) else ys
filter2 gt2 [1,3] = ff 1 (ff 3 [])
where gt2 x = x > 2
Uses nil list for seed for filtered result
Moving right to left folding function ff
applies filter predicate p
to next element
if holds, attaches element as head of filtered result; else omits
foldr
for length
length2 [1,2] = len 1 (len 2 0)
Uses seed value 0 as initial value of counter
Moving right to left folding function
len _ acc= acc + 1
takes next element as left argument and counter as right
returns incremented counter
foldr
for append
append2 [1,2] [3,4] = 1 : (2 : [3,4])
Uses entire second argument of ++
as seed
value
Moving right to left through left argument of ++
, folding
function (:)
foldr
, filter
, and
map
are
backward recursive functions
But think of them as powerful operators on whole lists
foldl
) foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f z [1,2,3] == f 1 (f 2 (f 3 z))
== 1 `f` (2 `f` (3 `f` z))
What about same functionality except group from left?
foldl
foldlX :: (a -> b -> a) -> a -> [b] -> a -- foldl
foldlX f z [] = z
foldlX f z (x:xs) = foldlX f (f z x) xs
Inserts “seed” value as leftmost element
Uses “seed” value parameter as accumulator—tail recursive
Has different type signature
If
$\oplus$
is an associative binary operation of type t -> t -> t
with identity element z
then,
for any finite xs
.
foldr (
$\oplus$) z xs = foldl (
$\oplus$) z xs
sum
, product
, and
concat
all satisfy
Which of foldr
or foldl
better
to use?
Strict function parameter means argument value always required by function evaluation
Nonstrict function parameter means argument value sometimes not required
Addition and multiplication strict in both parameters (operands)
++
strict in
first parameter and nonstrict in second
If operation
$\oplus$
nonstrict in either argument, then often better to use foldr
—exploits
lazy evaluation
If operations
$\oplus$
strict in both arguments, then more efficient to use foldl'
from library Data.List
foldr
or foldl
(1)Implement concat
with
foldr
because ++
nonstrict
in second
Implement sum
and product
with
foldl'
because +
an *
strict in
both
foldr
or foldl
(2)Uses foldl
Like length2
except len
arguments reversed
length2
better choice
because len
nonstrict list
argument
foldr
or foldl
(3)Similar to the tail recursive reverse
foldl
’s z
parameter initially nil
foldl
’s f
parameter uses (:)
to build
list in reverse order
reverse2
cannot exploit
lazy evaluation on (:)
’s right
argument because of its initialization
Better to use tail recursion
foldl
for foldr
foldr2 :: (a -> b -> b) -> b -> [a] -> b -- foldr
foldr2 f z xs = foldl flipf z (reverse xs)
where flipf y x = f x y
foldl
concatMap
)concatMap
for filter
First-class and higher-order functions
Generalizing computational patterns as higher-order functions
Using library of list-transforming functions
Thinking like a functional programmer
The Haskell code module for this section is in file HigherOrderFunctions.hs