列表理解 List Comprehensions

这些笔记应该与我们的教科书《Haskell 编程》的第 5 章结合起来阅读。

• We discuss some examples from the Haskell'98 standard prelude for pedagogical purposes.

• See the prelude for the current version of the language for all predefined classes and their instances.

Note:

请忽略这个声明，直到你读完本讲义最后的凯撒密码例子中的 编码和解码 部分。我们在这里提到它，是为了确保生成的 haskell 文件在开始时包含这个导入声明。

import Data.Char

基本概念

There is also a video on this section.

在数学中，comprehension 符号可以用来从现有的集合中构建新的集合。例如：

产生所有数字 $x^2$ 的集合 {1，4，9，16，25}，使得 x 是集合 {1...5} 的一个元素。

在 Haskell 中，类似的理解符号可以用来从旧列表中构造新的列表。比如说：

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

符号 | 读作 such that，<- 读作 drawn from，表达式 x <- [1 .. 5] 被称为 generator。一个生成器说明如何生成 x 的值。

Comprehension 可以有多个生成器，用逗号隔开。比如说：

> [(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)]

多重生成器就像嵌套的循环，后来的生成器是嵌套更深的循环，其变量变值更频繁。

依赖性生成器 Dependent Generators

There is also a video on this section.

后来的生成器可以依赖于早期生成器所引入的变量：

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

上述列表包括所有一对数字 (x,y)，使得 x,y 是列表 [1..3] 中的元素，并且 y >= x。

使用依赖性生成器，我们可以定义库函数，串联一个列表的列表。

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

For example:

> concat [[1,2,3],[4,5],[6]]
[1,2,3,4,5,6]

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

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

同样，计算一个列表的长度的库函数可以通过将每个元素替换为 1，并将得到的列表相加来定义。

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

在上述情况下，生成器 _ <- xs 只是作为一个计数器来控制产生适当数量的 1。

卫士 Guards

There is also a video on this section.

列表理解可以使用卫士来限制早期生成器所产生的值。如果防护措施是 true，那么当前的值将被保留；如果是 false，那么它们将被丢弃。

For example:

> [x | x <- [1..10], even x]
[2,4,6,8,10]

同样，一个将一个正整数映射到其正因子列表的函数可以通过以下方式定义。

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

For example:

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

如果一个正整数的因子只有 1 和它本身，那么它就是素数。因此，使用 factors 我们可以定义一个函数来决定一个数字是否是质数。

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

For example:

> prime 15
False

> prime 7
True

注意：决定一个数字如 15 不是质数并不需要函数 prime 产生所有的因子，因为在懒惰评估下，一旦产生除 1 以外的任何因子或数字本身，就会返回结果 False。

现在我们可以用一个卫兵来定义一个函数，它可以返回到一个给定极限的所有素数的列表：

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

For example:

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

压缩函数 The Zip Function

There is also a video on this section.

一个有用的库函数是 zip，它将两个列表映射为它们相应元素的对列表。

zip :: [a] -> [b] -> [(a,b)]

For example:

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

For example:

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

For example:

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

使用 zip 我们可以定义一个函数，返回一个列表中一个值的所有位置。

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

For example:

> positions 0 [1,0,0,1,0,1,1,0]
[1,2,4,7]

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

字符串的理解 String Comprehensions

There is also a video on this section.

字符串是一个用双引号括起来的字符序列。然而，在内部，字符串被表示为字符的列表。

例如，字符串 "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)]

同样地，列表理解也可以用来定义字符串的函数，比如计算一个字符在字符串中出现的次数：

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

For example:

> count 's' "Mississippi"
4

同样，我们可以定义一个函数，返回一个字符串中出现的小写字母和特定字符的数量：

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

For example

> lowers "Haskell"
6

扩展编程实例--凯撒密码 Extended Programming Example - The Caesar Cipher

There is also a video on this section.

凯撒密码是一种著名的字符串编码方法，尽管它是一种原始的编码方法。它只是将字符串中的每个字母替换为字母表中的 n 个位置（又称移位系数），在字母表的末尾处进行包裹。例如，字符串

"haskell is fun" would be encoded as "kdvnhoo lv ixq" (for n = 3).

"haskell is fun" would be encoded as "rkcuovv sc pex" (for n = 10).

编码和解码 Encoding and Decoding

在这个例子中，我们将使用一些关于字符的标准函数，这些函数在一个叫做 Data.Char 的库中提供，可以通过在脚本的开头加入以下声明加载到 Haskell 脚本中。

import Data.Char

注意：为了简单起见，我们只对字符串中的小写字母进行编码，其他字符如大写字母和标点符号不做改动。

让我们先定义一个函数 let2int，将一个小写字母转换为 0 到 25 之间的相应整数。我们还将定义相反的函数 int2let，将一个数字转换为相应的字母。

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

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

For example

> 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

For example:

> shift 3 'a'
'd'

> shift 3 'z'
'c'

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

现在我们可以定义 encode 函数，在列表理解中使用 shift 函数。

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

For example:

> encode 3 "haskell is fun"
"kdvnhoo lv ixq"

我们不需要一个单独的函数来解码一个字符串。我们可以重新使用 encode 函数，并为它提供一个负移位因子。

For example:

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

频率表 Frequency Tables

There is also a video on this section.

破解凯撒密码的关键是观察到一些字母在英语中的使用频率比其他字母高。通过分析大量的英语文本，我们可以得出以下近似的百分比频率。

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

For example:

> percent 5 15
33.333336

我们现在可以定义一个函数，为任何给定的字符串返回一个频率表：

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

For example:

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

破解密码 Cracking the Cipher

There is also a video on this section.

将观察到的频率列表 os 与预期频率列表 es 进行比较的标准方法是 chi-square statistic，它由以下和值定义：

其中 n 表示两个列表的长度。

注意：我们感兴趣的是，它产生的数值越小，两个频率列表之间的匹配就越好。上述公式可以转化为一个函数定义。

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

我们还定义了一个函数 rotate，它将一个列表中的元素向左旋转 n 位，在列表的开始处环绕，并假设整数参数 n 在 0 和列表的长度之间。

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

For example:

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

现在，假设我们得到了一个已编码的字符串，但不知道用于编码的移位系数，并希望确定这个数字，以便对字符串进行解码。我们怎样才能做到这一点呢？

我们可以通过制作编码字符串的频率表，计算该表相对于预期频率表的每种可能的旋转的卡方统计量，并使用最小卡方值的位置作为移位系数来实现。

For example, if we let

table' = freqs "kdvnhoo lv ixq"

then

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

gives the result

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

其中第 3 位出现的数值 202.42024 是最小值。我们得出结论，3 是我们用来编码这个字符串的最有可能的移位因素（我们知道是这样的！）。

现在我们可以写出破解密码的完整函数：

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

For example:

> crack "kdvnhoo lv ixq"
"haskell is fun"

> crack "vscd mywzboroxcsyxc kbo ecopev"
"list comprehensions are useful"

注意：crack函数可以解码大多数使用凯撒密码产生的字符串，然而，如果字符串很短或有一个不寻常的字母分布，它可能不会成功。

For example:

> crack (encode 3 "haskell")
"piasmtt"

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

练习

(1) 如果 $x^2 + y^2 = z^2$，那么正整数的三重（x,y,z）被称为 pythagorean。使用列表理解法，定义一个函数：

pyths :: Int -> [(Int,Int,Int)]

将一个整数 n 映射到所有这样的三联体，其组成部分在[1..n]。

For example:

> pyths 5
[(3,4,5),(4,3,5)]

答案

pyths :: Int -> [(Int,Int,Int)]
pyths n = [(x,y,z) | x <- ns, y <- ns, z <- ns, x^2 + y^2 = z^2]
 where ns <- [1 .. n]

(2) 如果一个正整数等于其所有因子的总和，不包括数字本身，那么它就是完美的。使用列表理解法，定义一个函数

perfects :: Int -> [Int]

返回到一个给定限制的所有完全数的列表。比如说：

> perfects 500
[6,28,496]

答案

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

perfects :: Int -> [Int]
perfects n = [x | x <- [1 .. n], sum (divisors x) == x]

(3) 两个长度为 n 的整数列表 xs 和 ys 的标量乘积由相应整数的乘积之和给出：

使用列表理解，定义一个函数，返回两个列表的标量乘积。

答案

f :: [Int] -> [Int] -> Int
f n m = sum [i * j | (i, j) <- zip n m]