程序代做CS代考 Haskell PROGRAMMING IN HASKELL – cscodehelp代写

PROGRAMMING IN HASKELL
Chapter 7 – Higher-Order Functions
0

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.
1

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.
2

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]
3

The map function can be defined in a particularly simple manner using a list comprehension:
mapfxs=[fx|x ← xs]
Alternatively, for the purposes of proofs, the map function can also be defined using recursion:
mapf[] =[]
map f (x:xs) = f x : map f xs
4

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]
5

Filter can be defined using a list comprehension:
filterpxs=[x|x ← xs,px] Alternatively, it can be defined using recursion:
filter p [] = []
filter p (x:xs)
| p x = x : filter p xs
| otherwise = filter p xs
6

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 ⊕ fxs
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.
7

For example:
sum[] =0
sum (x:xs) = x + sum xs
v=0 ⊕=+
v=1 ⊕=*
product [] = 1
product (x:xs) = x * product xs
and [] = True
and (x:xs) = x && and xs
v = True ⊕ = &&
8

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
9

Foldr itself can be defined using recursion:
foldr :: (a → b → b) → b → [a] → b foldrfv[] =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.
10

For example:
sum [1,2,3]
=
=
=
=
6
foldr (+) 0 [1,2,3]
foldr (+) 0 (1:(2:(3:[])))
1+(2+(3+0))
Replace each (:) by (+) and [] by 0.
11

For example:
product [1,2,3]
=
=
=
=
6
foldr (*) 1 [1,2,3]
foldr (*) 1 (1:(2:(3:[])))
1*(2*(3*1))
Replace each (:) by (*) and [] by 1.
12

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
13

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

Now recall the reverse function:
reverse [] = []
reverse (x:xs) = reverse xs ++ [x]
For example:
reverse [1,2,3]
=
=
=
[3,2,1]
Replace each (:) by λx xs → xs++[x]
and [] by [].
reverse (1:(2:(3:[])))
(([] ++ [3]) ++ [2]) ++ [1]
15

Hence, we have:
reverse = foldr (λx xs → xs ++ [x]) [] Finally, we note that the append function (++) has a
particularly compact definition using foldr:
(++ ys) = foldr (:) ys
Replace each (:) by (:) and [] by ys.
16

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.
17

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(gx)
For example:
odd :: Int → Bool odd = not . even
18

The library function all decides if every element of a list satisfies a given predicate.
all::(a → Bool) → [a] → Bool allpxs=and[px|x ← xs]
For example:
> all even [2,4,6,8,10]
True
19

Dually, the library function any decides if at least one element of a list satisfies a predicate.
any::(a → Bool) → [a] → Bool anypxs=or[px|x ← xs]
For example:
> any (== ’ ’) “abc def” True
20

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)
| p x = x : takeWhile p xs
| otherwise = []
For example:
> takeWhile (/= ’ ’) “abc def” “abc”
21

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)
| p x = dropWhile p xs
| otherwise = x:xs
For example:
> dropWhile (== ’ ’) ” abc” “abc”
22

Exercises
(1) Whatarehigher-orderfunctionsthatreturn functions as results better known as?
(2) Expressthecomprehension[fx|x←xs,px] using the functions map and filter.
(3) Redefine map f and filter p using foldr.
23