第 7 章：高阶函数（Higher-order functions）

原文：Graham Hutton, Programming in Haskell, Second Edition, Chapter 7。维护者已确认本书可翻译并发布用于学习研究。

本章介绍高阶函数，它们允许把常见编程模式封装为函数。我们先解释什么是高阶函数以及它们为什么有用，然后介绍标准 Prelude 中的一些高阶函数，最后实现一个二进制字符串传输器和两个投票算法。

7.1 基本概念（Basic concepts）

正如前几章所见，在 Haskell 中，带有多个参数的函数通常使用柯里化的概念来定义。也就是说，函数利用“函数可以返回函数作为结果”这一事实，一次接收一个参数。例如，定义：

add :: Int -> Int -> Int
add x y = x + y

表示：

add :: Int -> (Int -> Int)
add = \x -> (\y -> x + y)

它说明 add 是一个函数：接收整数 x 并返回一个函数，而这个函数再接收另一个整数 y 并返回它们的和 x + y。在 Haskell 中，也允许定义接收函数作为参数的函数。例如，一个函数接收一个函数和一个值，并把该函数对这个值应用两次，可以定义如下：

twice :: (a -> a) -> a -> a
twice f x = f (f x)

例如：

> twice (*2) 3
12
> twice reverse [1,2,3]
[1,2,3]

此外，因为 twice 是柯里化函数，所以它可以只用一个参数进行部分应用，从而构造其他有用函数。例如，函数 twice (*2) 会把一个数字变为原来的四倍；而“对一个有限列表反转两次没有效果”这个事实，可以用方程 twice reverse = id 捕捉，其中 id 是恒等函数，定义为 id x = x。

形式上，接收函数作为参数或返回函数作为结果的函数称为高阶函数（higher-order function）。不过在实践中，因为已经有术语 curried 用于描述返回函数作为结果的情况，所以 higher-order 通常只用来指“接收函数作为参数”。本章关注的就是后一种含义。

使用高阶函数会显著增强 Haskell 的能力，因为它允许把常见编程模式作为函数封装在语言内部。更一般地说，高阶函数可以用于在 Haskell 内部定义领域特定语言。例如，本章会呈现一个用于处理列表的简单语言；在本书第 II 部分中，我们还会为其他领域开发语言，包括交互式编程、带效果编程和构建解析器。

7.2 处理列表（Processing lists）

标准 Prelude 定义了许多用于处理列表的有用高阶函数。其中很多实际上是泛型函数，可以用于一系列不同类型；但这里我们只关注列表。第一个例子是函数 map，它把一个函数应用到列表中的所有元素上，可以使用列表推导式定义如下：

map :: (a -> b) -> [a] -> [b]
map f xs = [f x | x <- xs]

也就是说，map f xs 会返回所有值 f x 组成的列表，其中 x 是参数列表 xs 的元素。例如：

> map (+1) [1,3,5,7]
[2,4,6,8]
> map even [1,2,3,4]
[False,True,False,True]
> map reverse ["abc","def","ghi"]
["cba","fed","ihg"]

关于 map 还需要注意三点。首先，它是一个多态函数，可以应用到任意类型的列表上；大多数作用于列表的高阶函数也是如此。其次，它可以应用到自身，用于处理嵌套列表。例如，函数 map (map (+1)) 会把数字列表的列表中的每个数字都加一，如下面计算所示：

map (map (+1)) [[1,2,3],[4,5]]
= { applying the outer map }
[map (+1) [1,2,3], map (+1) [4,5]]
= { applying the inner maps }
[[2,3,4],[5,6]]

最后，函数 map 也可以使用递归定义：

map :: (a -> b) -> [a] -> [b]
map f []     = []
map f (x:xs) = f x : map f xs

也就是说，把一个函数应用到空列表的所有元素上会得到空列表；对于非空列表，则把函数应用到列表头部，然后继续把函数应用到尾部的所有元素。使用列表推导式给出的 map 原始定义更简单，但递归定义更适合用于推理（见第 16 章）。

另一个有用的高阶库函数是 filter，它选择列表中所有满足谓词的元素。所谓**谓词（predicate）**或性质，就是返回逻辑值的函数。与 map 一样，函数 filter 也有一个简单的列表推导式定义：

filter :: (a -> Bool) -> [a] -> [a]
filter p xs = [x | x <- xs, p x]

也就是说，filter p xs 返回所有值 x 组成的列表，其中 x 是列表 xs 的元素，并且 p x 的值为 True。例如：

> filter even [1..10]
[2,4,6,8,10]
> filter (> 5) [1..10]
[6,7,8,9,10]
> filter (/= ' ') "abc def ghi"
"abcdefghi"

与 map 一样，函数 filter 可以应用到任意类型的列表上，也可以为了推理目的用递归定义：

filter :: (a -> Bool) -> [a] -> [a]
filter p [] = []
filter p (x:xs) | p x       = x : filter p xs
                | otherwise = filter p xs

也就是说，从空列表中选择所有满足谓词的元素会得到空列表；对于非空列表，结果取决于列表头部是否满足谓词。如果满足，就保留头部，并继续过滤尾部；否则丢弃头部，只过滤尾部。

函数 map 和 filter 经常在程序中一起使用，其中 filter 用于从列表中选择某些元素，然后用 map 转换这些元素。例如，返回列表中所有偶数平方和的函数可以定义如下：

sumsqreven :: [Int] -> Int
sumsqreven ns = sum (map (^2) (filter even ns))

本节最后展示标准 Prelude 中定义的另外几个用于处理列表的高阶函数。

判断列表中的所有元素是否都满足某个谓词：

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

判断列表中是否存在元素满足某个谓词：

> any odd [2,4,6,8]
False

当元素满足某个谓词时，从列表中选择这些元素：

> takeWhile even [2,4,6,7,8]
[2,4,6]

当元素满足某个谓词时，从列表中移除这些元素：

> dropWhile odd [1,3,5,6,7]
[6,7]

7.3 foldr 函数（The foldr function）

许多接收列表作为参数的函数，都可以用下面这种简单的列表递归模式定义：

f []     = v
f (x:xs) = x # f xs

也就是说，这个函数把空列表映射为某个值 v，而把任意非空列表映射为把操作符 # 应用到列表头部以及递归处理尾部所得结果。许多熟悉的列表库函数都可以用这种递归模式定义：

sum []     = 0
sum (x:xs) = x + sum xs

product []     = 1
product (x:xs) = x * product xs

or []     = False
or (x:xs) = x || or xs

and []     = True
and (x:xs) = x && and xs

高阶库函数 foldr（fold right 的缩写）封装了这种用于定义列表函数的递归模式，其中操作符 # 和值 v 作为参数传入。例如，使用 foldr 后，上面四个定义可以更紧凑地改写如下：

sum :: Num a => [a] -> a
sum = foldr (+) 0

product :: Num a => [a] -> a
product = foldr (*) 1

or :: [Bool] -> Bool
or = foldr (||) False

and :: [Bool] -> Bool
and = foldr (&&) True

（回忆一下，当操作符作为参数使用时，必须写在圆括号中。）这些新定义也可以包含显式列表参数，例如：

sum xs = foldr (+) 0 xs

但我们更偏好上面那种通过部分应用让这些参数隐式出现的定义，因为它们更简单。

函数 foldr 本身可以使用递归定义：

foldr :: (a -> b -> b) -> b -> [a] -> b
foldr f v []     = v
foldr f v (x:xs) = f x (foldr f v xs)

也就是说，函数 foldr f v 把空列表映射为值 v，并把任意非空列表映射为把函数 f 应用到列表头部和递归处理后的尾部所得结果。不过在实践中，最好以非递归方式理解 foldr f v 的行为：它只是把列表中的每个 cons 操作符替换为函数 f，并把末尾的空列表替换为值 v。例如，把函数 foldr (+) 0 应用到列表：

1 : (2 : (3 : []))

会得到结果：

1 + (2 + (3 + 0))

其中 : 和 [] 分别被替换为 + 和 0。因此，定义 sum = foldr (+) 0 说明：对一个数字列表求和，就是把每个 cons 替换为加法，并把空列表替换为零。

尽管 foldr 封装的是一种简单递归模式，它所能定义的函数比初看上去多得多。首先，回忆库函数 length 的定义：

length :: [a] -> Int
length []     = 0
length (_:xs) = 1 + length xs

例如，把 length 应用到列表：

1 : (2 : (3 : []))

会得到结果：

1 + (1 + (1 + 0))

也就是说，计算列表长度，就是把每个 cons 替换为一个函数：该函数给第二个参数加一；并把空列表替换为零。因此，length 的定义可以使用 foldr 改写：

length :: [a] -> Int
length = foldr (\_ n -> 1+n) 0

现在考虑反转列表的库函数，它可以用显式递归简单定义如下：

reverse :: [a] -> [a]
reverse []     = []
reverse (x:xs) = reverse xs ++ [x]

例如，把 reverse 应用到列表：

1 : (2 : (3 : []))

会得到结果：

(([] ++ [3]) ++ [2]) ++ [1]

也许从这个定义或例子本身并不清楚 reverse 如何用 foldr 定义。不过，如果定义一个函数 snoc x xs = xs ++ [x]，它会把新元素加到列表末尾而不是开头（snoc 是 cons 的反写），那么 reverse 可以重新定义为：

reverse []     = []
reverse (x:xs) = snoc x (reverse xs)

由此立刻得到使用 foldr 的定义：

reverse :: [a] -> [a]
reverse = foldr snoc []

本节最后需要注意，fold right 这个名称反映了这样一种操作符使用方式：该操作符被假定向右结合。例如，求值 foldr (+) 0 [1,2,3] 会得到结果 1+(2+(3+0))，其中括号说明加法被假定向右结合。更一般地，foldr 的行为可以总结如下：

foldr (#) v [x0,x1,...,xn] = x0 # (x1 # (... (xn # v) ...))

7.4 foldl 函数（The foldl function）

也可以使用一个被假定向左结合的操作符来定义列表递归函数。例如，可以用一个辅助函数 sum' 来重新定义函数 sum。这个辅助函数接收一个额外参数 v，用于累积最终结果：

sum :: Num a => [a] -> a
sum = sum' 0
    where
        sum' v []     = v
        sum' v (x:xs) = sum' (v+x) xs

例如：

sum [1,2,3]
= { applying sum }
sum' 0 [1,2,3]
= { applying sum' }
sum' (0+1) [2,3]
= { applying sum' }
sum' ((0+1)+2) [3]
= { applying sum' }
sum' (((0+1)+2)+3) []
= { applying sum' }
((0+1)+2)+3
= { applying + }
6

这次计算中的括号说明，加法现在被假定向左结合。不过在这个例子中，结合顺序实际上不会影响结果的值，因为加法满足结合律。也就是说，对于任意数字 x、y 和 z，都有 x+(y+z) = (x+y)+z。

从 sum 这个例子推广开来，许多作用于列表的函数都可以用下面这种简单递归模式定义：

f v []     = v
f v (x:xs) = f (v # x) xs

也就是说，这个函数把空列表映射为累积值 v；而对于任意非空列表，它会用一个新的累积值递归处理尾部，这个新累积值通过把操作符 # 应用到当前值和列表头部得到。高阶库函数 foldl（fold left 的缩写）封装了这种递归模式，其中操作符 # 和累积值 v 作为参数传入。例如，使用 foldl 后，上面函数 sum 的定义可以更紧凑地改写如下：

sum :: Num a => [a] -> a
sum = foldl (+) 0

类似地，有：

product :: Num a => [a] -> a
product = foldl (*) 1

or :: [Bool] -> Bool
or = foldl (||) False

and :: [Bool] -> Bool
and = foldl (&&) True

上一节中的其他 foldr 例子，也可以通过提供适当操作符使用 foldl 重新定义：

length :: [a] -> Int
length = foldl (\n _ -> n+1) 0

reverse :: [a] -> [a]
reverse = foldl (\xs x -> x:xs) []

例如，使用这些新定义：

length [1,2,3] = ((0 + 1) + 1) + 1 = 3
reverse [1,2,3] = 3 : (2 : (1 : [])) = [3,2,1]

当一个函数既可以使用 foldr 也可以使用 foldl 定义时，就像上面的例子那样，通常会基于效率来选择更合适的定义，而这需要仔细考虑 Haskell 底层的求值机制。第 15 章会讨论这个问题。

函数 foldl 本身可以使用递归定义：

foldl :: (a -> b -> a) -> a -> [b] -> a
foldl f v []     = v
foldl f v (x:xs) = foldl f (f v x) xs

不过在实践中，与 foldr 一样，最好以非递归方式理解 foldl 的行为：它使用一个被假定向左结合的操作符 #，如下方程所总结：

foldl (#) v [x0,x1,...,xn] = (... ((v # x0) # x1) ...) # xn

7.5 组合操作符（The composition operator）

高阶库操作符 . 会返回两个函数的组合，将其作为单个函数，并且可以定义如下：

(.) :: (b -> c) -> (a -> b) -> (a -> c)
f . g = \x -> f (g x)

也就是说，f . g 读作 f composed with g，它是这样一个函数：接收参数 x，先把函数 g 应用于这个参数，再把函数 f 应用于得到的结果。这个操作符也可以定义为 (f . g) x = f (g x)。不过我们更偏好上面的定义，它使用 lambda 表达式把参数 x 推入定义主体，因为这显式表达了组合会返回一个函数作为结果。

组合可以简化嵌套函数应用：减少圆括号，并避免显式引用初始参数。例如，使用组合后，下面这些定义：

odd n = not (even n)
twice f x = f (f x)
sumsqreven ns = sum (map (^2) (filter even ns))

可以更简单地改写为：

odd = not . even
twice f = f . f
sumsqreven = sum . map (^2) . filter even

最后一个定义利用了组合满足结合律这一事实。也就是说，对于任何类型适当的函数 f、g 和 h，都有 f . (g . h) = (f . g) . h。因此，在三个或更多函数的组合中，例如 sumsqreven，不需要用圆括号指明结合顺序，因为结合律保证这不会影响结果。

组合还有一个单位元，也就是恒等函数：

id :: a -> a
id = \x -> x

也就是说，id 是简单返回其参数且不做改变的函数，并且对于任意函数 f，它满足性质 id . f = f 和 f . id = f。恒等函数在程序推理时经常有用，也为一串组合提供了合适起点。例如，函数列表的组合可以定义如下：

compose :: [a -> a] -> (a -> a)
compose = foldr (.) id

7.6 二进制字符串传输器（Binary string transmitter）

本章最后给出两个扩展编程例子。首先，考虑这样一个问题：模拟把一个字符串以低层形式作为二进制数字列表进行传输。

二进制数（Binary numbers）

由于人有十根手指，人们通常觉得使用以十为基数的十进制记法书写数字最方便。十进制数是由零到九之间的数字组成的序列，其中最右侧数字的权重为一，向左移动时每一位的权重都按十倍递增。例如，十进制数 2345 可以理解为：

2345 = (1000 * 2) + (100 * 3) + (10 * 4) + (1 * 5)

也就是说，2345 表示权重 1000、100、10、1 与数字 2、3、4、5 的乘积之和，其求值结果是整数 2345。

相比之下，计算机通常更方便使用更原始的二进制记法，即以二为基数的数字。二进制数是由零和一组成的序列，称为二进制数字或位（bits）。向左移动时，每一位的权重都按二倍递增。例如，二进制数 1101 可以理解为：

1101 = (8 * 1) + (4 * 1) + (2 * 0) + (1 * 1)

也就是说，1101 表示权重 8、4、2、1 与位 1、1、0、1 的乘积之和，其求值结果是整数 13。

为了简化某些函数的定义，在本例剩余部分中，我们假设二进制数以与通常相反的顺序书写。例如，1101 现在会写作 1011，向右移动时每一位的权重按二倍递增：

1011 = (1 * 1) + (2 * 0) + (4 * 1) + (8 * 1)

进制转换（Base conversion）

我们先导入包含实用字符函数的库：

import Data.Char

为了让我们定义的函数类型更有意义，声明一个位类型，把它作为整数类型的同义类型：

type Bit = Int

一个以位列表表示的二进制数，可以通过简单求取适当的加权和转换为整数：

bin2int :: [Bit] -> Int
bin2int bits = sum [w*b | (w,b) <- zip weights bits]
    where weights = iterate (*2) 1

高阶库函数 iterate 会通过把一个函数对一个值应用递增次数，产生一个无限列表：

iterate f x = [x, f x, f (f x), f (f (f x)), ...]

因此，bin2int 定义中的表达式 iterate (*2) 1 会产生权重列表 [1,2,4,8,...]，然后通过列表推导式用它计算加权和。例如：

> bin2int [1,0,1,1]
13

不过，借助一些代数可以发现一种更简单的 bin2int 定义。考虑任意四位二进制数 [a,b,c,d]。把 bin2int 应用于这个列表会产生加权和：

(1 * a) + (2 * b) + (4 * c) + (8 * d)

它可以重组如下：

(1 * a) + (2 * b) + (4 * c) + (8 * d)
= { simplifying 1 * a }
a + (2 * b) + (4 * c) + (8 * d)
= { factoring out 2 * }
a + 2 * (b + (2 * c) + (4 * d))
= { factoring out 2 * }
a + 2 * (b + 2 * (c + (2 * d)))
= { complicating d }
a + 2 * (b + 2 * (c + 2 * (d + 2 * 0)))

最终结果表明，把位列表 [a,b,c,d] 转换为整数，就相当于把每个 cons 替换为这样一个函数：它把第一个参数加到第二个参数的两倍上；并把空列表替换为零。更一般地，可以得出结论：bin2int 可以用 foldr 改写：

bin2int :: [Bit] -> Int
bin2int = foldr (\x y -> x + 2*y) 0

现在考虑相反方向的转换：从非负整数转换为二进制数。这可以通过反复把整数除以二并取余数来完成，直到整数变为零。例如，从整数 13 开始，过程如下：

13 divided by 2 = 6 remainder 1
6  divided by 2 = 3 remainder 0
3  divided by 2 = 1 remainder 1
1  divided by 2 = 0 remainder 1

余数序列 1011 给出了整数 13 的二进制表示。这个过程很容易用递归实现：

int2bin :: Int -> [Bit]
int2bin 0 = []
int2bin n = n `mod` 2 : int2bin (n `div` 2)

例如：

> int2bin 13
[1,0,1,1]

我们希望所有二进制数具有相同长度，这里是八位。为此，使用函数 make8，它会按需要截断或扩展一个二进制数，使其正好包含八位：

make8 :: [Bit] -> [Bit]
make8 bits = take 8 (bits ++ repeat 0)

库函数 repeat :: a -> [a] 会产生由某个值的副本组成的无限列表，但惰性求值会确保只有上下文真正需要的元素才会被产生。例如：

> make8 [1,0,1,1]
[1,0,1,1,0,0,0,0]

传输（Transmission）

现在可以定义一个函数，把字符串编码为位列表：先把每个字符转换为 Unicode 编号，再把每个这样的编号转换为八位二进制数，最后把这些二进制数连接起来，产生一个位列表。使用高阶函数 map 和组合，这个转换可以实现如下：

encode :: String -> [Bit]
encode = concat . map (make8 . int2bin . ord)

例如：

> encode "abc"
[1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]

为了对 encode 产生的位列表进行解码，先定义函数 chop8，它把这样的列表切分为八位二进制数：

chop8 :: [Bit] -> [[Bit]]
chop8 []   = []
chop8 bits = take 8 bits : chop8 (drop 8 bits)

现在可以很容易定义一个函数，把位列表解码为字符串：先切分列表，再把每个得到的二进制数转换为 Unicode 编号，然后转换为字符：

decode :: [Bit] -> String
decode = map (chr . bin2int) . chop8

例如：

> decode [1,0,0,0,0,1,1,0,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,0]
"abc"

最后，定义函数 transmit，它模拟把一个字符串作为位列表传输的过程。这里使用一个完美通信信道，并用恒等函数对其建模：

transmit :: String -> String
transmit = decode . channel . encode

channel :: [Bit] -> [Bit]
channel = id

例如：

> transmit "higher-order functions are easy"
"higher-order functions are easy"

7.7 投票算法（Voting algorithms）

第二个扩展编程例子中，我们考虑两种不同的选举胜者判定算法：简单的相对多数制（first past the post），以及更精细的选择投票制（alternative vote）。

相对多数制（First past the post）

在这个系统中，每个人有一票，得票数最多的候选人被宣布为胜者。例如，如果定义：

votes :: [String]
votes = ["Red", "Blue", "Green", "Blue", "Blue", "Red"]

那么候选人 "Green" 得一票，"Red" 得两票，而 "Blue" 得三票，因此 "Blue" 是胜者。我们并不把实现限制为用字符串表示候选人名字，而是利用 Haskell 的类系统，以更一般的方式定义函数。

首先，定义一个函数，用于计算某个给定值在列表中出现的次数，它适用于任何值可比较相等性的类型。这个函数可以用递归定义，但使用高阶函数会有更简单的定义：先选择列表中所有等于目标值的元素，再取所得列表的长度：

count :: Eq a => a -> [a] -> Int
count x = length . filter (== x)

例如：

> count "Red" votes
2

接着，高阶函数 filter 也可以用于定义一个函数，移除列表中的重复值：

rmdups :: Eq a => [a] -> [a]
rmdups []     = []
rmdups (x:xs) = x : filter (/= x) (rmdups xs)

例如：

> rmdups votes
["Red", "Blue", "Green"]

然后可以用列表推导式组合函数 count 和 rmdups，定义一个函数，按得票数递增顺序返回相对多数制选举的结果：

result :: Ord a => [a] -> [(Int,a)]
result vs = sort [(count v vs, v) | v <- rmdups vs]

例如：

> result votes
[(1,"Green"), (2,"Red"), (3,"Blue")]

上面使用的排序函数 sort :: Ord a => [a] -> [a] 由库 Data.List 提供。注意，由于二元组按字典序排序，所以得票数相同的候选人会由 result 按候选人名字顺序返回。最后，只需选择最后一个结果的第二个分量，就可以得到选举胜者：

winner :: Ord a => [a] -> a
winner = snd . last . result

例如：

> winner votes
"Blue"

选择投票制（Alternative vote）

在这个投票系统中，每个人可以给任意多或任意少的候选人投票，并按偏好顺序在选票上列出他们（第一选择、第二选择，依此类推）。为了确定胜者，首先移除所有空选票，然后从选票中淘汰第一选择票数最少的候选人，并重复同样过程，直到只剩下一名候选人，此人即被宣布为胜者。例如，如果定义：

ballots :: [[String]]
ballots = [["Red", "Green"],
           ["Blue"],
           ["Green", "Red", "Blue"],
           ["Blue", "Green", "Red"],
           ["Green"]]

那么第一张选票把 "Red" 作为第一选择，把 "Green" 作为第二选择；而第二张选票只选择了 "Blue"，依此类推。现在考虑这个例子中的胜者如何决定。首先，"Red" 的第一选择票数最少（只有一票），因此被淘汰：

[["Green"],
 ["Blue"],
 ["Green", "Blue"],
 ["Blue", "Green"],
 ["Green"]]

在这些修订后的选票中，候选人 "Blue" 现在第一选择票数最少（只有两票），因此也被淘汰：

[["Green"],
 [],
 ["Green"],
 ["Green"],
 ["Green"]]

移除现在为空的第二张选票后，"Green" 是唯一剩余候选人，因此是胜者。

使用 filter 和 map，可以很容易定义函数来移除空选票，并从每张选票中淘汰给定候选人：

rmempty :: Eq a => [[a]] -> [[a]]
rmempty = filter (/= [])

elim :: Eq a => a -> [[a]] -> [[a]]
elim x = map (filter (/= x))

和之前一样，这些函数以一般方式定义，而不是只针对字符串。接着，使用上一节中的函数 result，可以定义一个函数，它按照获得第一选择票数的递增顺序，对每张选票中的第一选择候选人排名：

rank :: Ord a => [[a]] -> [a]
rank = map snd . result . map head

例如：

> rank ballots
["Red", "Blue", "Green"]

最后，现在可以直接定义一个递归函数来实现选择投票制算法：

winner' :: Ord a => [[a]] -> a
winner' bs = case rank (rmempty bs) of
                 [c]    -> c
                 (c:cs) -> winner' (elim c bs)

也就是说，我们先移除空选票，然后按得票数递增顺序排列剩余的第一选择候选人。如果只剩下一名候选人，该候选人就是胜者；否则，淘汰第一选择票数最少的候选人，并重复整个过程。例如：

> winner' ballots
"Green"

最后需要注意，上面定义中使用的 Haskell case 机制允许在定义主体中使用模式匹配。有时，为了执行模式匹配而避免引入额外函数定义，这个机制很有用。

7.8 章注（Chapter remarks）

高阶函数的更多应用，包括生成计算机音乐、金融合约、图形图像、硬件描述、逻辑程序和 pretty printer，可以在 The Fun of Programming [9] 中找到。关于 foldr 的更深入教程见 [10]。

7.9 练习（Exercises）

1. 说明如何使用高阶函数 map 和 filter 重新表达列表推导式 [f x | x <- xs, p x]。

2. 不查看标准 Prelude 中的定义，定义下面这些作用于列表的高阶库函数。

   a. 判断列表中的所有元素是否都满足某个谓词：

all :: (a -> Bool) -> [a] -> Bool

b. 判断列表中是否有任意元素满足某个谓词：

any :: (a -> Bool) -> [a] -> Bool

c. 当元素满足谓词时，从列表中选择这些元素：

takeWhile :: (a -> Bool) -> [a] -> [a]

d. 当元素满足谓词时，从列表中移除这些元素：

dropWhile :: (a -> Bool) -> [a] -> [a]

注意：Prelude 中前两个函数是泛型函数，而不是专门针对列表类型的函数。

3. 使用 foldr 重新定义函数 map f 和 filter p。
4. 使用 foldl，定义函数 dec2int :: [Int] -> Int，它把十进制数转换为整数。例如：

> dec2int [2,3,4,5]
2345

5. 不查看标准 Prelude 中的定义，定义高阶库函数 curry，它把作用于二元组的函数转换为柯里化函数；反过来，定义函数 uncurry，它把带两个参数的柯里化函数转换为作用于二元组的函数。

提示：先写出这两个函数的类型。

6. 高阶函数 unfold 封装了一种产生列表的简单递归模式，可以定义如下：

unfold p h t x | p x       = []
               | otherwise = h x : unfold p h t (t x)

也就是说，如果谓词 p 对参数值为真，函数 unfold p h t 就产生空列表；否则，它会通过把函数 h 应用于该值来产生头部，并用函数 t 生成另一个参数，再以同样方式递归处理这个参数以产生列表尾部。例如，函数 int2bin 可以用 unfold 更紧凑地改写如下：

int2bin = unfold (== 0) (`mod` 2) (`div` 2)

使用 unfold 重新定义函数 chop8、map f 和 iterate f。

7. 修改二进制字符串传输器例子，使用奇偶校验位（parity bits）的概念检测简单传输错误。也就是说，编码期间产生的每个八位二进制数都扩展一个奇偶校验位：如果该数字包含奇数个 1，校验位设为一；否则设为零。反过来，解码期间消费每个所得九位二进制数时，要检查其奇偶校验位是否正确。如果正确，则丢弃校验位；否则报告奇偶校验错误。

提示：库函数 error :: String -> a 会把给定字符串显示为错误消息，并终止程序；多态结果类型确保 error 可以用于任意上下文。

8. 使用一个有故障的通信信道测试上一题中的新字符串传输程序。这个信道会忘记第一个位，可以用作用于位列表的函数 tail 建模。
9. 定义函数 altMap :: (a -> b) -> (a -> b) -> [a] -> [b]，它把两个参数函数交替应用到列表中的连续元素上。例如：

> altMap (+10) (+100) [0,1,2,3,4]
[10,101,12,103,14]

10. 使用 altMap 定义函数 luhn :: [Int] -> Bool，实现第 4 章练习中的 Luhn 算法，用于任意长度的银行卡号。用你自己的银行卡测试这个新函数。

练习 1-5 的解答见附录 A。