第 5 章：列表推导式（List comprehensions）

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

本章介绍列表推导式，它允许我们以简单方式定义许多作用于列表的函数。我们先解释生成器和守卫，然后介绍函数 zip 以及字符串推导式的思想，最后开发一个破解凯撒密码的程序。

5.1 基本概念（Basic concepts）

在数学中，可以使用推导式记法从已有集合构造新集合。例如，推导式 {x^2 | x ∈ {1..5}} 会产生集合 {1,4,9,16,25}，它包含所有这样的数字 x^2：其中 x 是集合 {1..5} 的元素。在 Haskell 中，可以使用类似的推导式记法从已有列表构造新列表。例如：

> [x^2 | x <- [1..5]]
[1,4,9,16,25]

符号 | 读作“使得”（such that），<- 读作“取自”（is drawn from），表达式 x <- [1..5] 称为生成器（generator）。一个列表推导式可以包含多个生成器，连续的生成器之间用逗号分隔。例如，下面可以产生所有可能的配对：从列表 [1,2,3] 中取一个元素，与从列表 [4,5] 中取一个元素组成一对：

> [(x,y) | x <- [1,2,3], y <- [4,5]]
[(1,4),(1,5),(2,4),(2,5),(3,4),(3,5)]

如果改变这个例子中两个生成器的顺序，会产生相同的配对集合，但排列顺序不同：

> [(x,y) | y <- [4,5], x <- [1,2,3]]
[(1,4),(2,4),(3,4),(1,5),(2,5),(3,5)]

具体来说，在这个例子中，配对中的 x 分量比 y 分量变化得更频繁（1,2,3,1,2,3 对比 4,4,4,5,5,5）；而在前一个例子中，y 分量比 x 分量变化得更频繁（4,5,4,5,4,5 对比 1,1,2,2,3,3）。可以把靠后的生成器看作嵌套得更深，因此它们的变量值比靠前的生成器变化得更频繁，这样就能理解这些行为。

靠后的生成器还可以依赖靠前生成器中变量的值。例如，列表 [1..3] 中元素的所有有序配对可以这样产生：

> [(x,y) | x <- [1..3], y <- [x..3]]
[(1,1),(1,2),(1,3),(2,2),(2,3),(3,3)]

作为这个思想的一个更实用例子，连接列表的列表的库函数 concat，可以用一个生成器依次选择每个列表，再用另一个生成器从每个列表中选择每个元素来定义：

concat :: [[a]] -> [a]
concat xss = [x | xs <- xss, x <- xs]

通配符模式 _ 有时在生成器中很有用，可以用来丢弃列表中的某些元素。例如，从一组二元组列表中选择所有第一分量的函数可以定义如下：

firsts :: [(a,b)] -> [a]
firsts ps = [x | (x,_) <- ps]

类似地，计算列表长度的库函数可以通过把每个元素替换成 1，再对得到的列表求和来定义：

length :: [a] -> Int
length xs = sum [1 | _ <- xs]

在这个例子中，生成器 _ <- xs 只是作为计数器，用来控制产生适当数量的 1。

5.2 守卫（Guards）

列表推导式还可以使用称为**守卫（guards）**的逻辑表达式，过滤由先前生成器产生的值。如果某个守卫为 True，当前值就会被保留；如果它为 False，当前值就会被丢弃。例如，推导式 [x | x <- [1..10], even x] 会产生列表 [2,4,6,8,10]，也就是列表 [1..10] 中的所有偶数。类似地，可以通过下面方式定义一个函数，它把正整数映射为其正因子列表：

factors :: Int -> [Int]
factors n = [x | x <- [1..n], n `mod` x == 0]

例如：

> factors 15
[1,3,5,15]
> factors 7
[1,7]

回忆一下，大于一的整数如果只有 1 和它自身这两个正因子，就称为素数。因此，使用 factors 可以简单定义一个函数，用于判断某个整数是否为素数：

prime :: Int -> Bool
prime n = factors n == [1,n]

例如：

> prime 15
False
> prime 7
True

注意，要判定像 15 这样的数字不是素数，并不需要函数 prime 产生它的所有因子，因为在惰性求值下，只要产生了除 1 和该数字本身之外的任何因子，就会返回结果 False。在这个例子中，这个因子就是 3。

回到列表推导式，现在使用 prime 就可以定义一个函数，用于产生不超过给定上限的所有素数：

primes :: Int -> [Int]
primes n = [x | x <- [2..n], prime x]

例如：

> primes 40
[2,3,5,7,11,13,17,19,23,29,31,37]

在第 15 章中，我们会介绍一个更高效的素数生成程序，它使用著名的埃拉托斯特尼筛法（sieve of Eratosthenes）。借助惰性求值的思想，这个算法在 Haskell 中可以得到特别清晰简洁的实现。

作为关于守卫的最后一个例子，假设我们用键和值的二元组列表表示一张查找表。那么，对于任何支持相等比较的键类型，都可以定义一个函数 find，它返回表中与给定键关联的所有值：

find :: Eq a => a -> [(a,b)] -> [b]
find k t = [v | (k',v) <- t, k == k']

例如：

> find 'b' [('a',1),('b',2),('c',3),('b',4)]
[2,4]

5.3 zip 函数（The zip function）

库函数 zip 会从两个已有列表中依次取元素组成二元组，从而产生一个新列表，直到其中一个列表或两个列表都耗尽为止。例如：

> zip ['a','b','c'] [1,2,3,4]
[('a',1),('b',2),('c',3)]

函数 zip 在使用列表推导式编程时经常很有用。例如，假设我们定义一个函数，它返回列表中所有相邻元素组成的二元组：

pairs :: [a] -> [(a,a)]
pairs xs = zip xs (tail xs)

例如：

> pairs [1,2,3,4]
[(1,2),(2,3),(3,4)]

使用 pairs，现在可以定义一个函数来判断任意有序类型元素组成的列表是否已排序：只需检查列表中所有相邻元素对是否都处于正确顺序：

sorted :: Ord a => [a] -> Bool
sorted xs = and [x <= y | (x,y) <- pairs xs]

例如：

> sorted [1,2,3,4]
True
> sorted [1,3,2,4]
False

与函数 prime 类似，要判断列表 [1,3,2,4] 未排序，也许不需要函数 sorted 产生所有相邻元素对，因为只要产生任何不满足顺序的元素对，就会返回结果 False。在这个例子中，这个元素对就是 (3,2)。

使用 zip，还可以定义一个函数，它返回某个值在列表中出现的所有位置。做法是把每个元素与它的位置配对，然后选择那些出现了目标值的位置：

positions :: Eq a => a -> [a] -> [Int]
positions x xs = [i | (x',i) <- zip xs [0..], x == x']

例如：

> positions False [True, False, True, False]
[1,3]

在 positions 的定义中，表达式 [0..] 会产生索引列表 [0,1,2,3,...]。这个列表在概念上是无限的，但在惰性求值下，只有使用它的上下文真正需要的元素才会被产生。在这里，它与输入列表 xs 进行 zip，因此实际只会产生所需数量的索引。用这种方式利用惰性求值，可以避免显式产生一个与输入列表等长的索引列表。

5.4 字符串推导式（String comprehensions）

到目前为止，我们把字符串看作 Haskell 中的基本概念。事实上，字符串并不是原始概念，而是由字符列表构造而成。例如，字符串 "abc" :: String 只是字符列表 ['a','b','c'] :: [Char] 的缩写。因为字符串就是列表，任何作用于列表的多态函数也可以用于字符串。例如：

> "abcde" !! 2
'c'
> take 3 "abcde"
"abc"
> length "abcde"
5
> zip "abc" [1,2,3,4]
[('a',1),('b',2),('c',3)]

出于同样原因，列表推导式也可以用于定义作用于字符串的函数，例如分别返回一个字符串中小写字母数量和某个特定字符出现次数的函数：

lowers :: String -> Int
lowers xs = length [x | x <- xs, x >= 'a' && x <= 'z']

count :: Char -> String -> Int
count x xs = length [x' | x' <- xs, x == x']

例如：

> lowers "Haskell"
6
> count 's' "Mississippi"
4

5.5 凯撒密码（The Caesar cipher）

本章最后用一个扩展编程例子收尾。考虑这样一个问题：为了隐藏字符串内容，需要对它进行编码。一个著名的编码方法是凯撒密码，它以 Julius Caesar 在 2000 多年前使用这种方法而得名。为了编码字符串，Caesar 只是把字符串中的每个字母替换为字母表中后移三位的字母，并在字母表末尾回绕。例如，字符串：

"haskell is fun"

会被编码为：

"kdvnhoo lv ixq"

更一般地，Caesar 使用的特定偏移因子 3 可以替换为 1 到 25 之间的任意整数，从而得到 25 种不同的字符串编码方式。例如，如果偏移因子为 10，上面的原始字符串会被编码如下：

"rkcuovv sc pex"

本节剩余部分会展示如何使用 Haskell 实现凯撒密码，以及如何利用英文本中字母频率的信息轻松破解这个密码。

编码与解码（Encoding and decoding）

我们将使用一些作用于字符的标准函数，它们由名为 Data.Char 的库提供。可以在脚本开头包含下面的声明，把这个库加载到 Haskell 脚本中：

import Data.Char

为简单起见，我们只编码字符串中的小写字母，而让大写字母、标点等其他字符保持不变。首先定义一个函数 let2int，把 'a' 到 'z' 之间的小写字母转换为对应的 0 到 25 之间的整数；同时定义一个执行相反转换的函数 int2let：

let2int :: Char -> Int
let2int c = ord c - ord 'a'

int2let :: Int -> Char
int2let n = chr (ord 'a' + n)

（库函数 ord :: Char -> Int 和 chr :: Int -> Char 用于在字符及其 Unicode 编号之间进行转换。）例如：

> let2int 'a'
0
> int2let 0
'a'

使用这两个函数，可以定义一个函数 shift，它把偏移因子应用于小写字母：先把字母转换为对应整数，再加上偏移因子，并取除以 26 后的余数（从而在字母表末尾回绕），最后把得到的整数转换回小写字母：

shift :: Int -> Char -> Char
shift n c | isLower c = int2let ((let2int c + n) `mod` 26)
          | otherwise = c

（库函数 isLower :: Char -> Bool 用于判断一个字符是否为小写字母。）注意，这个函数接受正数和负数偏移因子，而且只会改变小写字母。例如：

> shift 3 'a'
'd'
> shift 3 'z'
'c'
> shift (-3) 'c'
'z'
> shift 3 ' '
' '

现在，在列表推导式中使用 shift，就可以轻松定义一个函数，用给定偏移因子编码字符串：

encode :: Int -> String -> String
encode n xs = [shift n x | x <- xs]

不需要单独定义解码字符串的函数，因为这只需使用负偏移因子即可。例如：

> encode 3 "haskell is fun"
"kdvnhoo lv ixq"
> encode (-3) "kdvnhoo lv ixq"
"haskell is fun"

频率表（Frequency tables）

破解凯撒密码的关键在于：英文文本中某些字母比其他字母更常用。通过分析大量英文文本，可以得到下面这张字母表中 26 个字母近似百分比频率表：

table :: [Float]
table = [8.1, 1.5, 2.8, 4.2, 12.7, 2.2, 2.0, 6.1, 7.0,
         0.2, 0.8, 4.0, 2.4, 6.7, 7.5, 1.9, 0.1, 6.0,
         6.3, 9.0, 2.8, 1.0, 2.4, 0.2, 2.0, 0.1]

例如，字母 'e' 出现最频繁，频率为 12.7%；而 'q' 和 'z' 出现最少，频率仅为 0.1%。为单个字符串生成频率表也很有用。为此，我们先定义一个函数，用于计算一个整数相对于另一个整数的百分比，并以浮点数形式返回结果：

percent :: Int -> Int -> Float
percent n m = (fromIntegral n / fromIntegral m) * 100

（库函数 fromIntegral :: Int -> Float 会把整数转换为浮点数。）例如：

> percent 5 15
33.333336

现在，在列表推导式中使用 percent，并结合上一节中的函数 lowers 和 count，可以定义一个函数，为任意给定字符串返回频率表：

freqs :: String -> [Float]
freqs xs = [percent (count x xs) n | x <- ['a'..'z']]
    where n = lowers xs

例如：

> freqs "abbcccddddeeeee"
[6.666667, 13.333334, 20.0, 26.666668, ..., 0.0]

也就是说，字母 'a' 出现的频率约为 6.6%，字母 'b' 的频率约为 13.3%，依此类推。在 freqs 中使用局部定义 n = lowers xs，可以确保参数字符串中的小写字母数量只计算一次，而不是在列表推导式中使用这个数字的 26 次里每次都重新计算。

破解密码（Cracking the cipher）

比较一组观察频率 os 和一组期望频率 es 的标准方法是卡方统计量（chi-square statistic）。它由下面这个求和公式定义，其中 n 表示两个列表的长度，xs_i 表示列表 xs 中从零开始计数的第 i 个元素：

sum [((os_i - es_i)^2) / es_i | i <- [0..n-1]]

这里不必关心卡方统计量的细节，只需知道它产生的值越小，两组频率列表匹配得越好。使用库函数 zip 和列表推导式，可以很容易把上面的公式翻译成函数定义：

chisqr :: [Float] -> [Float] -> Float
chisqr os es = sum [((o-e)^2)/e | (o,e) <- zip os es]

接着，定义一个函数，把列表中的元素向左旋转 n 位，并在列表开头回绕；这里假定整数参数 n 位于零到列表长度之间：

rotate :: Int -> [a] -> [a]
rotate n xs = drop n xs ++ take n xs

例如：

> rotate 3 [1,2,3,4,5]
[4,5,1,2,3]

现在假设我们得到一个已编码字符串，但不知道编码时使用的偏移因子，并希望确定这个数字以便解码字符串。通常可以这样完成：先生成编码字符串的频率表，然后针对这张表的每一种可能旋转，计算它与期望频率表之间的卡方统计量，并把最小卡方值的位置作为偏移因子。例如，如果令 table' = freqs "kdvnhoo lv ixq"，那么：

[chisqr (rotate n table') table | n <- [0..25]]

会给出结果：

[1408.8524, 640.0218, 612.3969, 202.42024, ..., 626.4024]

其中最小值 202.42024 出现在这个列表的位置 3。因此，我们得出结论：3 最可能是用于编码该字符串的偏移因子。使用本章前面的函数 positions，这个过程可以实现如下：

crack :: String -> String
crack xs = encode (-factor) xs
    where
        factor = head (positions (minimum chitab) chitab)
        chitab = [chisqr (rotate n table') table | n <- [0..25]]
        table' = freqs xs

例如：

> crack "kdvnhoo lv ixq"
"haskell is fun"
> crack "vscd mywzboroxcsyxc kbo ecopev"
"list comprehensions are useful"

更一般地，函数 crack 可以解码大多数使用凯撒密码产生的字符串。不过请注意，如果字符串很短，或者字母分布不同寻常，它可能不会成功。例如：

> crack (encode 3 "haskell")
"piasmtt"
> crack (encode 3 "boxing wizards jump quickly")
"wjsdib rduvmyn ephk lpdxfgt"

5.6 章注（Chapter remarks）

术语 comprehension 来自集合论中的概括公理（axiom of comprehension），它精确表达了通过选择所有满足某个特定性质的值来构造集合这一思想。Haskell Report [4] 给出了列表推导式的形式化含义，它通过翻译为语言中更原始的特性来完成。关于凯撒密码以及许多其他著名密码方法的通俗介绍，可参见 The Code Book [7]。

5.7 练习（Exercises）

1. 使用列表推导式，给出一个表达式来计算前一百个整数平方的和：1^2 + 2^2 + ... + 100^2。

2. 假设大小为 m * n 的坐标网格由所有整数对 (x,y) 组成，其中 0 <= x <= m 且 0 <= y <= n。使用列表推导式定义一个函数 grid :: Int -> Int -> [(Int,Int)]，它返回给定大小的坐标网格。例如：

> grid 1 2
[(0,0),(0,1),(0,2),(1,0),(1,1),(1,2)]

3. 使用列表推导式和上面的函数 grid，定义一个函数 square :: Int -> [(Int,Int)]，它返回大小为 n 的坐标方格，并排除从 (0,0) 到 (n,n) 的对角线。例如：

> square 2
[(0,1),(0,2),(1,0),(1,2),(2,0),(2,1)]

4. 以函数 length 的类似方式，说明如何使用列表推导式定义库函数 replicate :: Int -> a -> [a]，它产生由相同元素组成的列表。例如：

> replicate 3 True
[True,True,True]

5. 正整数三元组 (x,y,z) 如果满足方程 x^2 + y^2 = z^2，就称为毕达哥拉斯三元组（Pythagorean triple）。使用带有三个生成器的列表推导式，定义一个函数 pyths :: Int -> [(Int,Int,Int)]，它返回所有分量不超过给定上限的这类三元组。例如：

> pyths 10
[(3,4,5),(4,3,5),(6,8,10),(8,6,10)]

6. 如果一个正整数等于它的所有因子之和（不包括该数字本身），它就是完全数（perfect number）。使用列表推导式和函数 factors，定义一个函数 perfects :: Int -> [Int]，它返回不超过给定上限的所有完全数。例如：

> perfects 500
[6,28,496]

7. 说明如何把带有两个生成器的列表推导式 [(x,y) | x <- [1,2], y <- [3,4]]，重新表达为两个只带单个生成器的推导式。提示：把一个推导式嵌套在另一个推导式中，并使用库函数 concat :: [[a]] -> [a]。

8. 使用函数 find 重新定义函数 positions。

9. 两个长度为 n 的整数列表 xs 和 ys 的标量积（scalar product），定义为对应整数乘积之和：

sum [xs_i * ys_i | i <- [0..n-1]]

以 chisqr 的类似方式，说明如何用列表推导式定义函数 scalarproduct :: [Int] -> [Int] -> Int，它返回两个列表的标量积。例如：

> scalarproduct [1,2,3] [4,5,6]
32

10. 修改凯撒密码程序，使其也能处理大写字母。

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