Programming in Haskell: Chapter 7 - Higher-Order Functions

PROGRAMMING IN HASKELL
Chapter 7 - Higher-Order Functions
1
Introduction
A function is called higher-order if it takes a function

as an argument or returns a function as a result.
twice :: (a  a)  a  a
twice f x = f (f x)
twice is higher-order because it

takes a function as its first argument.
2
Why Are They Useful?
 Common programming idioms can be encoded

as functions within the language itself.
 Domain specific languages can be defined as

collections of higher-order functions.
 Algebraic properties of higher-order functions

can be used to reason about programs.
3
The Map Function
The higher-order library function called map applies

a function to every element of a list.
map :: (a  b)  [a]  [b]
For example:
> map (+1) [1,3,5,7]
[2,4,6,8]
4
The map function can be defined in a particularly
simple manner using a list comprehension:
map f xs = [f x | x  xs]
Alternatively, for the purposes of proofs, the map

function can also be defined using recursion:
map f [] = []
map f (x:xs) = f x : map f xs
5
The Filter Function
The higher-order library function filter selects every

element from a list that satisfies a predicate.
filter :: (a  Bool)  [a]  [a]
For example:
> filter even [1..10]
[2,4,6,8,10]
6
Filter can be defined using a list comprehension:
filter p xs = [x | x  xs, p x]
Alternatively, it can be defined using recursion:
filter p [] = []
filter p (x:xs)
|px = x : filter p xs
| otherwise = filter p xs
7
The Foldr Function
A number of functions on lists can be defined using

the following simple pattern of recursion:
f [] = v
f (x:xs) = x  f xs
f maps the empty list to some value v, and

any non-empty list to some function 
applied to its head and f of its tail.
8
For example:
sum [] = 0
=0
v
sum (x:xs) = x + sum xs =

+
product [] = 1
v=1
product (x:xs) = x * product xs =
*
v=
and [] = True
and (x:xs) = x && and xs
True
 = &&
9
The higher-order library function foldr (fold right)
encapsulates this simple pattern of recursion, with
the function  and the value v as arguments.
For example:
sum = foldr (+) 0
product = foldr (*) 1
or = foldr (||) False
and = foldr (&&) True

10
Foldr itself can be defined using recursion:
foldr :: (a  b  b)  b  [a]  b
foldr f v [] =v
foldr f v (x:xs) = f x (foldr f v xs)
However, it is best to think of foldr non-recursively,

as simultaneously replacing each (:) in a list by a
given function, and [] by a given value.
11
For example:
sum [1,2,3]
=
foldr (+) 0 [1,2,3]
=
foldr (+) 0 (1:(2:(3:[])))
=
1+(2+(3+0))
=
6
Replace each (:)
by (+) and [] by 0.
12
For example:
product [1,2,3]
=
foldr (*) 1 [1,2,3]
=
foldr (*) 1 (1:(2:(3:[])))
=
1*(2*(3*1))
=
6
Replace each (:)
by (*) and [] by 1.
13
Other Foldr Examples
Even though foldr encapsulates a simple pattern

of recursion, it can be used to define many more
functions than might first be expected.
Recall the length function:
length :: [a]  Int

length [] =0
length (_:xs) = 1 + length xs
14
For example:
length [1,2,3]
=
length (1:(2:(3:[])))
=
1+(1+(1+0))
=
3 Replace each (:)
by _ n  1+n
Hence, we have: and [] by 0.
length = foldr (_ n  1+n) 0

15
Now recall the reverse function:
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
For example:
Replace each (:) by
x xs  xs ++ [x]
reverse [1,2,3] and [] by [].
=
reverse (1:(2:(3:[])))
=
(([] ++ [3]) ++ [2]) ++ [1]
=
[3,2,1]
16
Hence, we have:
reverse = foldr (x xs  xs ++ [x]) []
Finally, we note that the append function (++) has a

particularly compact definition using foldr:
Replace each
(++ ys) = foldr (:) ys
(:) by (:) and
[] by ys.
17
Why Is Foldr Useful?
 Some recursive functions on lists, such as sum,

are simpler to define using foldr.
 Properties of functions defined using foldr can

be proved using algebraic properties of foldr,
such as fusion and the banana split rule.
 Advanced program optimisations can be simpler

if foldr is used in place of explicit recursion.
18
Other Library Functions
The library function (.) returns the composition of

two functions as a single function.
(.) :: (b  c)  (a  b)  (a  c)
f . g = x  f (g x)
For example:
odd :: Int  Bool

odd = not . even
19
The library function all decides if every element of
a list satisfies a given predicate.
all :: (a  Bool)  [a]  Bool

all p xs = and [p x | x  xs]
For example:
> all even [2,4,6,8,10]
True
20
Dually, the library function any decides if at least
one element of a list satisfies a predicate.
any :: (a  Bool)  [a]  Bool

any p xs = or [p x | x  xs]
For example:
> any (== ’ ’) "abc def"
True
21
The library function takeWhile selects elements from
a list while a predicate holds of all the elements.
takeWhile :: (a  Bool)  [a]  [a]

takeWhile p [] = []
takeWhile p (x:xs)
|px = x : takeWhile p xs
| otherwise = []
For example:
> takeWhile (/= ’ ’) "abc def"
"abc"
22
Dually, the function dropWhile removes elements
while a predicate holds of all the elements.
dropWhile :: (a  Bool)  [a]  [a]

dropWhile p [] = []
dropWhile p (x:xs)
|px = dropWhile p xs
| otherwise = x:xs
For example:
> dropWhile (== ’ ’) " abc"
"abc"
23
Exercises
(1) What are higher-order functions that return

functions as results better known as?
(2) Express the comprehension [f x | x  xs, p x]

using the functions map and filter.
(3) Redefine map f and filter p using foldr.
24

Programming in Haskell: Chapter 7 - Higher-Order Functions

Uploaded by

Copyright:

Available Formats

Programming in Haskell: Chapter 7 - Higher-Order Functions

Uploaded by

Document Information

Original Title

Copyright

Available Formats

Share this document

Share or Embed Document

Sharing Options

Did you find this document useful?

Is this content inappropriate?

Copyright:

Available Formats

Programming in Haskell: Chapter 7 - Higher-Order Functions

Uploaded by

Copyright:

Available Formats

What are higher-order functions?

What are higher-order functions?

What is the map function and how can it be defined using foldr?

What is the map function and how can it be defined using foldr?

PROGRAMMING IN HASKELL

Chapter 7 - Higher-Order Functions

A function is called higher-order if it takes a function

twice is higher-order because it

 Common programming idioms can be encoded

 Domain specific languages can be defined as

 Algebraic properties of higher-order functions

The higher-order library function called map applies

map :: (a  b)  [a]  [b]

> map (+1) [1,3,5,7]

Alternatively, for the purposes of proofs, the map

The higher-order library function filter selects every

filter :: (a  Bool)  [a]  [a]

> filter even [1..10]

Alternatively, it can be defined using recursion:

A number of functions on lists can be defined using

f maps the empty list to some value v, and

sum (x:xs) = x + sum xs =

sum = foldr (+) 0

product = foldr (*) 1

or = foldr (||) False

and = foldr (&&) True

However, it is best to think of foldr non-recursively,

Even though foldr encapsulates a simple pattern

Recall the length function:

length :: [a]  Int

length = foldr (_ n  1+n) 0

reverse = foldr (x xs  xs ++ [x]) []

Finally, we note that the append function (++) has a

 Some recursive functions on lists, such as sum,

 Properties of functions defined using foldr can

 Advanced program optimisations can be simpler

The library function (.) returns the composition of

odd :: Int  Bool

all :: (a  Bool)  [a]  Bool

> all even [2,4,6,8,10]

any :: (a  Bool)  [a]  Bool

> any (== ’ ’) "abc def"

takeWhile :: (a  Bool)  [a]  [a]

> takeWhile (/= ’ ’) "abc def"

dropWhile :: (a  Bool)  [a]  [a]

> dropWhile (== ’ ’) " abc"

(1) What are higher-order functions that return

(2) Express the comprehension [f x | x  xs, p x]

(3) Redefine map f and filter p using foldr.

You might also like