Skip to main content

高阶函数 Higher-order Functions

这些笔记应该与我们的教科书《Haskell 编程》的第 7 章 - 高阶函数结合起来阅读。

Note:​

请忽略这个声明，直到你阅读了本讲义最后的二进制字符串发送器例子中的 Base Conversion 部分。我们在这里提到它，是为了确保生成的 haskell 文件在开始时包含这个导入语句。

import Data.Char

基本概念​

There is also a video on this section.

如果一个函数以一个函数为参数或以一个函数为结果返回，则该函数被称为 higher-order。

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

For example:

> twice (*2) 3
12

> twice (+10) 5
25

> twice (\ x -> x ^ 2) 3
81

> twice reverse [1,2,3]
[1,2,3]

函数 twice 是高阶的，因为它把一个函数作为其第一个参数。

为什么它们是有用的？​

高阶函数允许更多可重用的代码，例如 twice 函数显示了我们如何多次应用同一个函数。map 函数是另一个代码可重用的好例子。

处理清单​

There is also a video on this section.

The Map Function​

高阶库函数 map，对列表中的每个元素都应用一个函数。

map :: (a -> b) -> [a] -> [b]

For example:

> map (+1) [1,3,5,7]
[2,4,6,8]

> map (^3) [1,3,5,7]
[1,27,125,343]

> map reverse ["conversation", "talking", "discussion"]
["noitasrevnoc","gniklat","noissucsid"]

map 函数可以用一个特别简单的方式来定义，使用列表理解：

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

另外，为了证明的目的，也可以用递归来定义地图函数：

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

The Filter Function​

高阶库函数 filter 从一个列表中选择满足一个谓词的每个元素。

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

For example:

> filter even [1..10]
[2,4,6,8,10]

过滤器可以用列表理解法来定义：

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

另外，也可以用递归法来定义：

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

The Foldr Function​

There is also a video on this section.

可以用以下简单的递归模式来定义列表上的一些函数：

f :: Num a => [a] -> a
f []     = v
f (x:xs) = x # f xs

函数 f 将空列表映射到某个值 v，将任何非空列表映射到某个应用于其头部和尾部 f 的函数 #。

For example:

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

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

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

高阶库函数 foldr（fold right）封装了这种简单的递归模式，以函数 # 和值 v 作为参数。

For example:

sum = foldr (+) 0

product = foldr (*) 1

or = foldr (||) False

and = foldr (&&) True

foldr 本身可以用递归来定义：

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

然而，最好是以非递归的方式来考虑 foldr，即同时用一个给定的函数替换列表中的每个 (:)，用一个给定的值替换 []，总结如下。

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

For example:

sum [1,2,3]
= foldr (+) 0 [1,2,3]
= foldr (+) 0 (1:(2:(3:[])))
= 1+(2+(3+0))
= 6

用 (+) 替换每个 (:)，用 0 替换 []。

product [1,2,3]
= foldr (*) 1 [1,2,3]
= foldr (*) 1 (1:(2:(3:[])))
= 1*(2*(3*1))
= 6

用 (*) 代替每个 (:)，用 1 代替 []。

Other Foldr Examples​

尽管 foldr 封装了一个简单的递归模式，但它可以用来定义比最初预期更多的函数。

回顾一下长度函数：

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

For example:

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

我们可以将每个 (:) 替换为 _ n -> 1+n，[] 替换为 0，从而得到：

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

现在回忆一下反向功能：

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

For example:

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

用 x xs -> xs ++ [x] 替换每个（:），用 [] 替换 []。因此，我们有：

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

最后，我们注意到，附加函数（++）有一个特别紧凑的定义，使用 foldr。

(++ ys) = foldr (:) ys

这里我们用 (:) 代替每个 (:)，用 ys 代替 []。

一个更简洁的定义如下：

(++) = foldr (:)

The Foldl Function​

There is also a video on this section.

也可以在列表上定义递归函数，使用一个假定为向左联想的操作符。

例如，可以用这种方式重新定义函数 sum，即使用一个辅助函数 sum，它需要一个额外的参数 v，用于累积最终结果：

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

For example

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

从上面的 sum 例子推而广之，许多列表上的函数可以用以下简单的递归模式来定义。

f :: Num a => a -> [a] -> a
f v []     = v
f v (x:xs) = f (v # x) xs

也就是说，该函数将空列表映射为 _ 累加器值 v，将任何非空列表映射为使用新的累加器值递归处理尾部的结果，该值是通过对当前值和列表头部应用运算符 # 得到的。

上述 sum 函数可以使用高阶库函数 foldl（fold left）重写为。

The above sum function can be re-written using the higher-order library function foldl (fold left) as:

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

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

foldl 函数可以用递归来定义：

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

然而，最好是以非递归的方式来考虑 foldl，即假定与左边的运算符 # 相关联，正如以下公式所总结的那样。

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

The Composition Operator​

There is also a video on this section.

库函数（.）将两个函数的组合作为一个单一的函数返回。

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

也就是说，f . g 被理解为 f composed with g，是指接受一个参数 x 的函数，将函数 g 应用于这个参数，并将函数 f 应用于结果。

组成可以用来简化嵌套函数的应用，通过减少括号和避免明确地引用初始参数的需要。

For example:

odd :: Int -> Bool
odd n = not (even n)

可以定义为：

odd :: Int -> Bool
odd = not . even

同样地，以下定义

twice :: (a -> a) -> a -> a
twice f x = f (f x)
sumsqreven :: Integral a => [a] -> a
sumsqreven ns = sum (map (^2) (filter even ns))

可以更简单地改写为（添加素数，以赋予这些不同的名称）：

twice' :: (a -> a) -> a -> a
twice' f = f . f

sumsqreven' :: Integral a => [a] -> a
sumsqreven' = sum . map (^2) . filter even

Other Library Functions​

库函数 all 决定一个列表中的每个元素是否满足一个给定的谓词。

all :: (a -> Bool) -> [a] -> Bool
all p xs = and [p x | x <- xs]

For example:

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

> all odd [1,3,7,9,10]
False

同样，库函数 any 决定一个列表中是否至少有一个元素满足一个谓词。

any :: (a -> Bool) -> [a] -> Bool
any p xs = or [p x | x <- xs]

For example:

> any (== ' ') "abc def"
True

> any (> 10) [1,5,4,8,7]
False

库函数 takeWhile 从一个列表中选择元素，同时一个谓词持有所有元素。

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

For example:

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

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

同样地，函数 dropWhile 在一个谓词对所有元素成立的情况下删除元素。

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

For example:

> dropWhile (== 'a') "aaabcadef"
"bcadef"

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

Programming Example - Binary String Transmitter 二进制字符串发射器​

There is also a video on this section.

二进制数是由零和一组成的序列，称为 bits，当我们向左移动时，连续的比特的重量增加了 2 倍。

例如，二进制数字 1101 可以理解为如下：

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

为了简化某些函数的定义，在本例的其余部分，我们假设二进制数是按逆序书写的。

例如，1101 现在将被写成 1011，当我们向右移动时，连续的比特的权重将增加 2 倍：

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

基地转换 Base Conversion​

我们首先导入字符的有用函数库，并将比特的类型声明为整数类型的同义词：

import Data.Char
type Bit = Int

我们可以使用 bin2int 函数将一个二进制数（以比特列表表示）转换为整数：

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)
= a + (2 * b) + (4 * c) + (8 * d)
= a + 2 * (b + (2 * c) + (4 * d))
= a + 2 * (b + 2 * (c + (2 * d)))
= a + 2 * (b + 2 * (c + 2 * (d + 2 * 0)))

从上面的结果，我们可以看到，转换可以写成将每个 cons 替换成将其第一个参数加到第二个参数两倍的函数，并将空列表替换成 0。因此，bin2int 可以改写为（使用稍微不同的名称）：

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

将非负整数转换为二进制数的相反函数可以写成：

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

For example:

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

现在我们可以定义一个函数make8，确保我们有相同长度的二进制数，即 8 比特。它可以根据情况截断或扩展一个二进制数，使其成为 8 位长：

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

For example:

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

传动装置 Transmission​

There is also a video on this section.

我们现在可以定义一个函数，通过将每个字符转换为 Unicode 数字，将每个这样的数字转换为 8 位二进制数字，并将这些数字串联起来产生一个比特列表，从而将一串字符编码为比特列表。

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

For example:

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

为了解码一个比特列表，我们首先定义了一个函数 chop8，将这样的列表切成八位二进制数字。

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

现在我们可以定义 decode 函数，该函数将一个比特列表切开，将每个产生的二进制数字转换为 Unicode 数字，然后再转换为字符。

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

For example:

> 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

For example:

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

上面的例子实际上是封装了三个功能，即编码、传输和解码。我们可以把编码和解码的步骤分开，看看中间发生了什么。通道是一个身份函数，也就是说，它输出任何作为输入的东西。

> encode "higher-order functions are easy"
[0,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,0,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,1,0,1,0,0,1,1,1,1,0,1,1,0,0,1,0,0,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,0,1,1,0,0,0,1,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,0]

> decode [0,0,0,1,0,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,0,1,1,0,0,0,0,1,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,1,0,1,0,0,1,1,1,1,0,1,1,0,0,1,0,0,1,1,1,0,0,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,0,1,1,0,0,0,1,0,1,1,1,0,1,0,0,1,0,1,1,0,1,1,1,1,0,1,1,0,0,1,1,1,0,1,1,0,1,1,0,0,1,1,1,0,0,0,0,0,0,1,0,0,1,0,0,0,0,1,1,0,0,1,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,0,1,0,0,1,0,1,0,0,1,1,0,1,0,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,0,0,1,1,1,1,0]
"higher-order functions are easy"

练习​

(1) 将函数作为结果返回的高阶函数更被称为什么？

(2) Express the comprehension [f x | x <- xs, p x] using the functions map and filter. The function type is given as:

fun :: Num a => (a -> a) -> (a -> Bool) -> [a] -> [a]

For example:

> fun (^2) even [1..20]
[4,16,36,64,100,144,196,256,324,400]

> fun (^2) odd [1..20]
[1,9,25,49,81,121,169,225,289,361]

(3) Redefine map f and filter p using foldr. For your reference, here are the definitions of map and filter from lecture notes.

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

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

(4) Define a function altMap :: (a -> b) -> (a -> b) -> [a] -> [b] that alternatively applies the two argument functions to successive elements in a list.

For example:

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