第 9 章 - 快速检查与随机测试（Quick checks and random tests）

本章内容包括：

• 使用随机值
• 构建一个小型属性测试框架
• 使用流行的测试框架 QuickCheck
• 为特殊测试用例定制随机值生成器
• 为软件项目配备测试套件

前几章一直在为各种应用编写 Haskell 代码，但我们还没有认真问过一个问题：写出来的代码真的正确吗？它做了应该做的事吗？算法产生了正确结果吗？在软件工程中，这个问题通常通过测试来回答。本章将探索测试，重点介绍流行的测试库 QuickCheck，并在 Haskell 语境中学习属性测试，也就是如何为纯函数代码形式化正确性属性。

本章先介绍属性测试概念，然后实现一个自己的小型测试框架。在此过程中，我们会学习如何在 Haskell 中处理随机值。随后介绍 QuickCheck，说明如何编写属性、使用 Arbitrary 类型类，并根据需要修改测试行为。最后，本章会展示如何把 QuickCheck 测试套件整合到 Stack 项目中。

9.1 如何测试（How to test）

测试可以在不同层级上完成。集成测试关注不同软件组件之间的协作，系统测试检查完成后的系统是否满足需求，而单元测试更关注较小的代码“单元”，并单独测试其行为。这样我们可以编写自包含测试，验证较小独立组件是否正确工作。图 9.1 展示了这种结构。

图 9.1 测试金字塔

集成测试和系统测试的有效性依赖单元测试已经暗示出的正确性。如果不能确信系统中最小的组件按预期工作，从外部测试整个软件也没有意义。因此，我们试图通过测试获得的软件信任，取决于最底层自包含测试的彻底程度。本章聚焦单元测试，以及如何为单个函数构造这些测试。

一个简单的测试方式是基于示例：为代码指定某些输入，并测试运行后是否产生预先确定的结果。这种方式简单，但有明显缺点：

• 每个测试输入都必须手工编写。
• 测试覆盖度与测试用例数量相关。
• 边界情况必须手动指定，而且可能被遗忘。

这很容易出错。如果每次写代码时都能想出完整测试集，实际上也就不太需要测试了。最后，我们往往只为已经知道能正常工作的功能编写测试，尤其当测试设计者也是实现者时更是如此。这样的测试更像是防止回归的保险，却很少真正帮助我们发现错误。

这正是属性测试发挥作用的地方。当我们把正确功能形式化为输入和输出之间应当成立的数学属性时，就可以随机生成输入，并在每个输入上检查该属性。这样更可能发现错误，因为不需要手工指定测试输入。

9.1.1 属性测试（Property testing）

先思考“属性”是什么意思。属性是数据中可计算并可验证的特征。简单地说，一个接收某个参数并返回布尔值的函数就可以被视为属性。用于测试软件功能时，属性可以任意复杂：可以比较基础值，可以检查数据是否遵循某组规则，也可以组合多个属性构造新的属性。基于相等性的测试，即检查代码输出是否等于预定义值，是属性测试的一种简单形式。

先看一个例子。假设要测试某种排序函数。该函数的一个属性可以是：输出始终是已排序列表。我们可以构造一个函数，检查某个列表是否升序排序，再构造一个函数，检查某个函数对给定输入的输出是否已排序。

代码清单 9.1 列表有序性的谓词

sorted :: Ord a => [a] -> Bool
sorted [] = True                                      -- #1
sorted [_] = True                                     -- #1
sorted (x : y : xs) = x <= y && sorted (y : xs)       -- #2

sorts :: Ord a => ([a] -> [a]) -> [a] -> Bool
sorts f input = sorted $ f input                      -- #3

• #1 空列表和单元素列表总是有序
• #2 检查相邻元素顺序并递归处理尾部
• #3 检查函数输出是否有序

现在，可以用 sorts 属性测试某些输入。sorted 是属性，而 sorts 在给定输入上测试函数是否满足该属性：

ghci> import Data.List (sort)
ghci> sort `sorts` [5,4,3,2,1 :: Int]
True
ghci> sort `sorts` [1,3,2,5,4 :: Int]
True
ghci> sort `sorts` ([] :: [Int])
True

这似乎很好。不过，为了构造测试套件，我们不想手写这样的测试用例，而是希望随机化输入。随机性会让我们离开纯函数世界，构造别的东西。

9.1.2 生成随机值（Generating random values）

属性测试是一种随机化测试技术，因此我们需要花一些时间处理随机输入生成。一个好的框架不仅需要支持许多已有随机生成器的类型，也要支持修改这些生成器。为复杂数据类型构建新生成器应当简单。

我们先关注如何为排序属性测试创建随机列表。随机值在 Haskell 中比较特殊，因为随机生成器需要跟踪状态，才能计算新的随机数。在带副作用语言中，随机值通常通过某个全局状态实现；但在 Haskell 中，函数输出只能由输入决定。

假设要创建一个生成随机值的函数。它必须接收某个随机状态，并返回随机值；同时还必须返回新的随机状态，否则后续调用会一直使用同一个状态。下面的例子展示了这种机制。

代码清单 9.2 显式处理随机状态的函数

newtype RandomState = RandomState Int deriving (Eq, Show) -- #1

randomInt :: RandomState -> (Int, RandomState)
randomInt (RandomState rs) = (newRs, RandomState newRs)   -- #2
  where
    newRs = (1103515245 * rs + 12345) `mod` (2 ^ 31)      -- #3

randomIntList :: RandomState -> Int -> [Int]
randomIntList rs n
  | n <= 0 = []                                           -- #4
  | otherwise =
    let (v, rs') = randomInt rs
     in v : randomIntList rs' (n - 1)

• #1 用整数包装一个随机状态
• #2 生成一个值并返回新状态
• #3 使用线性同余生成器计算伪随机值
• #4 重复推进状态来生成列表

ghci> randomIntList (RandomState 100) 5
[829870797,1533044610,1478614675,1357823696,413847241]

这是一种生成随机数的方式，但不够通用。我们需要描述数字以外的随机值，也不必自己实现这些功能。System.Random 模块提供了许多函数，可生成不同类型的随机值。

要使用该模块，需要在 package.yaml 的依赖中加入 random：

dependencies:
- random >= 1.2.1.1

System.Random 提供大量函数、类型和类型类。不过其中一些已经弃用，不应使用。写作本书时，更现代的方式位于 System.Random.Stateful 模块。它提供许多随机生成器类型及交互方式。本章只处理常见伪随机生成器 StdGen。

9.1.3 Random 与 Uniform

使用 StdGen 与前面自己创建的 RandomState 很相似：

ghci> import System.Random
ghci> import System.Random.Stateful
ghci> g = mkStdGen 100
ghci> random g :: (Int, StdGen)
(9216477508314497915,StdGen {...})

可以用种子创建 StdGen，并用 random 生成随机数和修改后的 StdGen。创建随机值时有四个重要函数：

• random :: (Random a, RandomGen g) => g -> (a, g)
• randomR :: (Random a, RandomGen g) => (a, a) -> g -> (a, g)
• uniform :: (Uniform a, RandomGen g) => g -> (a, g)
• uniformR :: (UniformRange a, RandomGen g) => (a, a) -> g -> (a, g)

random 会生成某个类型的随机值，但该类型可能值分布未知；uniform 则为给定类型生成均匀分布随机值。这就是两个函数约束中类型类不同的原因。两个函数也都有带范围的版本，后缀为 R。

由于 Random 和 Uniform 都有许多实例，我们可以编写多态随机函数，不必只为 Int 或数值类型编写。下面把随机列表生成泛化，并让生成器产生随机长度。

代码清单 9.3 生成随机大小随机列表的函数

randomListN :: (Random a) => StdGen -> Int -> ([a], StdGen)
randomListN gen n
  | n <= 0 = ([], gen)
  | otherwise =
    let (v, gen') = random gen                      -- #1
        (xs, gen'') = randomListN gen' (n - 1)      -- #2
     in (v : xs, gen'')

randomList :: (Random a) => StdGen -> Int -> ([a], StdGen)
randomList gen maxVal = randomListN gen' n          -- #3
  where
    (n, gen') = uniformR (0, maxVal) gen             -- #4

randomList' :: (Random a) => StdGen -> ([a], StdGen)
randomList' = flip randomList 100                    -- #5

• #1 从生成器取出一个随机值
• #2 把新生成器传给递归调用
• #3 用随机长度生成列表
• #4 随机选择列表长度
• #5 默认最大长度为 100

和 RandomState 一样，我们把修改后的生成器传给递归调用以产生新随机值。最终返回修改后的生成器，以便继续使用。不过，一直显式传入和返回生成器很繁琐。我们可能希望像多数语言那样使用全局随机值生成器。

9.1.4 使用全局随机生成器（Using a global random value generator）

在 Haskell 这样的语言中，有状态全局值似乎不可能，但 System.Random 提供了相关功能。简化后的两个动作是：

• getStdGen :: IO StdGen
• setStdGen :: StdGen -> IO ()

它们允许在 IO 动作中访问和设置全局 StdGen。全局 StdGen 在程序启动时已预初始化。不过这里有一个陷阱：getStdGen 返回的不是全局生成器的引用，而是一份副本。因此修改后必须把新生成器写回全局状态。

注意 全局资源可以借助 IORef 在 IO 动作中实现，getStdGen 和 setStdGen 就是如此。IORef 是可变引用，可用于读取、存储和修改全局可访问数据。不过这种实现并不适合并发使用，因此不推荐，只作为演示。稍后会使用更安全的 applyAtomicGen 和 globalStdGen。

使用全局生成器，可以编写一个不需要 StdGen 参数的 IO 动作：先取出全局生成器，应用 randomList'，再写回修改后的生成器，并返回随机列表。

代码清单 9.4 生成随机列表的 IO 动作

randomListIO :: (Random a) => IO [a]
randomListIO = do
  g <- getStdGen                         -- #1
  let (xs, g') = randomList' g           -- #2
  setStdGen g'                           -- #3
  return xs                              -- #4

• #1 读取全局生成器
• #2 生成随机列表和新生成器
• #3 写回新生成器
• #4 返回随机列表

不过，这段代码使用了在并发场景下不应使用的旧函数。System.Random.Stateful 提供了更安全的新接口。我们可以使用 AtomicGenM 和 globalStdGen，后者的类型正是 AtomicGenM StdGen。要对它使用类似 random 的函数，可以使用 applyAtomicGen：

ghci> applyAtomicGen random globalStdGen :: IO Int
-8749052575918541620
ghci> applyAtomicGen (uniformR (0, 100)) globalStdGen :: IO Float
60.164364
ghci> applyAtomicGen randomList' globalStdGen :: IO [Bool]
[True,False,False,True,...]

这个函数本质上执行了与 randomListIO 相同的动作：读取全局生成器，在修改它的同时生成值，再写回全局引用。但它以原子方式完成，因此在并发上下文中安全。由于 globalStdGen 是常量，可以写一个便利函数：

代码清单 9.5 将函数应用到全局伪随机生成器的 IO 动作

applyGlobalStdGen :: (StdGen -> (a, StdGen)) -> IO a
applyGlobalStdGen f = applyAtomicGen f globalStdGen -- #1

现在，可以在 IO 动作中轻松且安全地生成随机值，从而编写一个简单属性测试。

9.1.5 基础属性测试（A basic property test）

构造属性测试的最后一部分，是把所有组件组合成一个 IO 动作：生成一定数量测试用例，在它们上面测试给定函数，并在发现反例时打印输入。

代码清单 9.6 检查函数是否正确排序输入的属性测试示例

propertyTestSorts :: ([Int] -> [Int]) -> Int -> IO ()
propertyTestSorts f n
  | n <= 0 = putStrLn "Tests successful!"             -- #1
  | otherwise = do
    xs <- applyGlobalStdGen randomList'               -- #2
    if f `sorts` xs                                   -- #3
      then propertyTestSorts f $ n - 1                -- #4
      else putStrLn $ "Test failed on: " <> show xs   -- #5

• #1 所有测试完成时报告成功
• #2 生成随机输入
• #3 检查属性
• #4 成功则继续下一轮
• #5 失败则打印反例

可以进一步泛化属性测试：把被测函数、测试输出的谓词，以及生成随机值的 IO 动作都作为参数。

代码清单 9.7 通用属性测试动作

propertyTest :: Show a => (a -> b) -> (b -> Bool) -> IO a -> Int -> IO ()
propertyTest fun predicate random n
  | n <= 0 = putStrLn "Tests successful!"             -- #1
  | otherwise = do
    testCase <- random                                -- #2
    if predicate $ fun testCase                       -- #3
      then propertyTest fun predicate random $ n - 1  -- #4
      else putStrLn $ "Test failed on: " <> show testCase -- #5

这个定义已经相当通用。假设 sort 确实会排序，而 id 不会：

ghci> propertyTest sort sorted (applyGlobalStdGen randomList' :: IO [Int]) 100
Tests successful!
ghci> propertyTest id sorted (applyGlobalStdGen randomList' :: IO [Int]) 100
Test failed on: [...]

现在，我们已经有了一个基础属性测试思路。不过，还有一些问题需要讨论。

9.1.6 为随机值定义后置条件（Defining postconditions for random values）

随机值生成器有时会产生不适合测试的值。例如，如果某个属性只对非空列表有意义，那么随机生成空列表就没有帮助。解决方式之一是给生成器加上后置条件：生成一个值后，如果它不满足条件，就重新生成。

我们可以把随机生成器包装成一个类型，以便组合它们：

代码清单 9.8 随机值生成器的类型和智能构造器

newtype RandomIO a = RandomIO {runRandomIO :: IO a}

one :: Random a => RandomIO a
one = RandomIO $ applyGlobalStdGen random

suchThat :: RandomIO a -> (a -> Bool) -> RandomIO a
suchThat rio p = RandomIO $ do
  x <- runRandomIO rio
  if p x
    then return x
    else runRandomIO (rio `suchThat` p)

suchThat 的行为类似过滤器：不断生成值，直到得到满足谓词的值。

有时还需要重复某个 IO 动作，得到一个列表：

代码清单 9.9 重复 IO 动作的聚合函数

replicateIO :: Int -> IO a -> IO [a]
replicateIO n action
  | n <= 0 = return []
  | otherwise = do
    x <- action
    xs <- replicateIO (n - 1) action
    return (x : xs)

还可以修改随机值生成器的输出：

代码清单 9.10 修改随机值生成器输出的函数

mapRandomIO :: (a -> b) -> RandomIO a -> RandomIO b
mapRandomIO f rio = RandomIO $ f <$> runRandomIO rio

练习：随机值的 Functor

suchThat 或多或少像随机生成器上的 filter。我们还没有构建等价于 map 的函数。为了保持尽可能通用，请为 RandomIO 实现 Functor 类型类实例，其中 fmap 会把函数应用到随机值上。

现在可以构造适合生成可读字符和字符串的生成器。先生成 ASCII 字符，再基于它构建字符串：

代码清单 9.11 随机 ASCII 字符和字符串生成器

asciiChar :: RandomIO Char
asciiChar = one `suchThat` (\c -> isAscii c && not (isControl c)) -- #1

letterChar :: RandomIO Char
letterChar = asciiChar `suchThat` isLetter                       -- #2

manyOf :: RandomIO a -> RandomIO [a]
manyOf rio = RandomIO $ do                                       -- #3
  n <- applyGlobalStdGen $ uniformR (0, 100)
  replicateIO n (runRandomIO rio)

asciiString :: RandomIO String
asciiString = manyOf asciiChar                                   -- #4

letterString :: RandomIO String
letterString = manyOf letterChar                                 -- #4

• #1 生成可读 ASCII 字符
• #2 生成字母字符
• #3 生成随机长度列表
• #4 基于字符生成器构造字符串生成器

现在可以生成测试用的随机字符串：

ghci> runRandomIO asciiString
"N:=P!RVyo7O{=QU6"
ghci> runRandomIO letterString
"EdgcdiBHQcwIJAkCKlhemiaUWBMeNxrHOkWigRuktokfMyxXzYklFBO"

有了自定义生成器后，可以把 propertyTest 简化为接收一个返回 Bool 的谓词和一个 RandomIO 生成器。

代码清单 9.12 使用自定义随机值生成器的属性测试动作

propertyTest :: Show a => (a -> Bool) -> RandomIO a -> Int -> IO ()
propertyTest predicate random n
  | n <= 0 = putStrLn "Tests successful!"       -- #1
  | otherwise = do
    testCase <- runRandomIO random              -- #2
    if predicate testCase                       -- #3
      then propertyTest predicate random $ n - 1
      else putStrLn $ "Test failed on: " <> show testCase

练习：高效 ASCII 字符串

当前 letterString 定义效率很低。它先从巨大集合中随机选择，再过滤掉不想要的元素。请编写一个函数，接收非空元素列表，并从中随机选择一个元素。然后用它构建更快的 ASCII 和字母生成器：

elements :: [a] -> RandomIO a
elements [] = error "elements cannot work with an empty list!"
elements xs = ...

9.2 随机化测试（Randomized testing）

在深入研究随机值生成器之后，可以更认真地思考如何处理属性。也就是说，我们需要弄清楚如何编写能够保证程序正确性的属性。

首先，把目前创建的测试代码放入名为 Test.SimpleCheck 的模块中，作为我们的测试框架。随后，把第 2 章的凯撒密码项目代码复制到源码中，并开始为它编写测试。

应该测试什么属性？这高度依赖软件规格。在我们的例子中，只想确保关于代码的核心假设成立。其中一个假设是：对某个值应用两次 ROT13 会得到原值。因此，ROT13 是对称的。对任意输入 s，必须有 s == rot13 (rot13 s)。

代码清单 9.13 ROT13 对称性的属性测试

propRot13Symmetrical :: IO ()
propRot13Symmetrical =
  propertyTest
    (\s -> s == rot13 (rot13 s)) -- #1
    asciiString                  -- #2
    100                          -- #3

• #1 属性本身
• #2 使用可读 ASCII 字符串作为输入
• #3 测试 100 个用例

随机值生成器的选择很重要。第 2 章中，我们说这个对称属性对字母成立。但这里测试的是更一般情况：所有人类可读 ASCII 字符。因此，这不仅测试 rot13 是否对称，也测试这种对称性在输入中出现其他字符时是否健壮。幸运的是，我们就是这样构建 rot13 的，因此测试会成功。

这个测试可以看作规格测试。ROT13 的对称性是规格的一部分。这个属性确保完成后的 rot13 函数正确实现该规格。现在可以重构 rot13 及其底层机制，而不必担心破坏规格。如果出错，测试应当能告诉我们。

注意 在代码中给属性测试一个特殊名字是好习惯。一些代码库用 prop 或 prop_ 前缀。若代码库同时包含属性测试和基于示例的单元测试，后者有时会使用 test 或 test_ 前缀。

还可以更深入测试辅助函数。例如 alphabetRot 用于让字符在字母表中旋转。一个必须成立的属性是：旋转后的字符必须仍然是原字母表中的元素。不过这个函数输入比之前复杂：它接收 Alphabet、Int 和 Char，且 Char 必须是第一个参数的元素。我们可以为这个测试创建专门生成器：生成非空字母表，并从该字母表中随机选择字符。

代码清单 9.14 字母表旋转封闭性的属性测试

propAlphabetRotClosed :: IO ()
propAlphabetRotClosed = propertyTest prop gen 100       -- #1
  where
    prop (alphabet, n, c) =                              -- #2
      let c' = alphabetRot alphabet n c
       in c' `elem` alphabet

    gen = RandomIO $ do
      alphabet <-                                        -- #3
        runRandomIO $
          asciiString `suchThat` (not . null)
      n <- runRandomIO $ elements [-100 .. 100]          -- #4
      c <- runRandomIO $ elements alphabet               -- #5
      return (L.nub alphabet, n, c)                      -- #6

生成器在这个测试中承担了主要工作，为测试提供合理基础。传给测试前，它会去除字母表中的重复项，并从随机字母表中专门随机选择字符。

9.2.1 引用透明性的好处（The benefit of referential transparency）

这里短暂讨论为什么属性测试在 Haskell 中尤其有效。到目前为止，我们利用了语言的一个重要方面：Haskell 是纯的。这意味着我们编写的函数本质上没有副作用。函数结果只由输入决定。也就是说，观察输入和输出就足以判断函数是否正确，因为系统中没有其他输出或行为需要观察。此外，只需要为函数设计随机值生成器，不必搭建额外环境。

这种性质也称为引用透明性。任何引用透明表达式，例如纯函数应用，都可以直接替换为该表达式求值后的值。我们只需要确认表达式求出的值符合预期。

以第 2 章中的 isMisc 为例。它判断某个字符既不是字母也不是数字。项目中还有 isLower、isUpper 和 isDigit 等谓词。隐含性质是：当且仅当这些其他谓词都不为真时，isMisc 才为真。

代码清单 9.15 检查谓词不变量的属性测试

propIsMiscIsDefault :: IO ()
propIsMiscIsDefault =
  propertyTest
    (\c -> isMisc c == not (isLower c || isUpper c || isDigit c)) -- #1
    one                                                          -- #2
    10000                                                       -- #3

这里的属性是一个简单谓词，用于检查 isMisc 与一个逻辑项的等价性。正是因为 Haskell 是纯的，才可以用简单的 == 检查两个项的等价性。需要注意，这些项只是观察上等价：对给定输入产生相同输出，但技术行为和内存占用可能不同。在纯代码中，就程序正确性而言，观察等价已经足够。

现在我们已经掌握属性测试的大致思路，可以从自己的小框架升级到真正的测试强者：QuickCheck。

9.3 QuickCheck 测试框架（The QuickCheck testing framework）

本章开始时，我们构建了自己的小测试框架 SimpleCheck。不过它有几个很难忽视的问题：

• 构造随机值生成器复杂且费力。
• 属性组合困难。
• 无法了解被测数据，例如测试了哪些值、出现频率如何。
• 无法通过前置条件修改测试。
• 随机值生成器行为固定，不容易改变。
• 失败用例不会被最小化，可能又大又难懂。

这些问题会让框架在真实世界中很难使用。QuickCheck 正是这些问题的答案。QuickCheck 最初由 Koen Claessen 和 John Hughes 于 1999 年在查尔姆斯理工大学开发，它普及了属性测试概念，并被许多语言重新实现。它的设计与我们的 SimpleCheck 很相似，提供：

• 测试属性的函数
• 用于组合和修改属性的组合子
• 调试测试行为的辅助功能
• 用于随机值生成的类型和类型类

要把 QuickCheck 引入项目，只需在 package.yaml 依赖中加入：

dependencies:
- base >= 4.7 && < 5
- QuickCheck >= 2.0
- random >= 1.2.1.1

9.3.1 在 QuickCheck 中使用 Property

最基础的构件是 quickCheck 函数。它接收某个属性作为输入，并为我们测试它，生成一个 IO 动作。Bool 和 QuickCheck 的 Property 类型都是属性的重要实例。此外，返回属性的函数本身也可以是属性。因此，一个返回 Bool 的函数，例如简单谓词，也是属性。

注意 在内部，属性必须拥有 Testable 类型类实例。该类定义如何把某个类型转换成属性。本章不需要自定义实例，但在文档中看到 Testable prop 时，知道它与属性有关即可。

和之前一样，测试 rot13 的对称性：

ghci> import Test.QuickCheck
ghci> prop_rot13Symm s = s == rot13 (rot13 s)
ghci> :t prop_rot13Symm
prop_rot13Symm :: String -> Bool
ghci> quickCheck prop_rot13Symm
++ OK, passed 100 tests.

QuickCheck 成功测试了这个属性。值得注意的是，它似乎神奇地为函数创建了输入数据。稍后会探索这个机制。

如果用一个错误实现测试会怎样？

ghci> symbols = upperAlphabet ++ lowerAlphabet ++ digits
ghci> rot13' = map $ (\ch -> if ch `elem` symbols then alphabetRot symbols 13 ch else ch)
ghci> prop_rot13Symm s = s == rot13' (rot13' s)
ghci> quickCheck prop_rot13Symm
*** Failed! Falsified (after 2 tests and 1 shrink):
"a"

这里故意创建了一个错误的 rot13 实现。QuickCheck 告诉我们测试失败，并给出输入 "a"。这和旧的属性测试函数类似，但 QuickCheck 还做了 shrink。

shrink 的含义是：测试用例失败时，QuickCheck 会自动尝试让它更小，例如数值变小、列表和映射元素更少。缩小后的值仍必须是反例，否则 QuickCheck 会保留更大的值。这样可以得到更容易理解的反例。

我们在自己的 SimpleCheck 中可能得到一长串随机字符串，而 QuickCheck 会稳定地收缩到 "a"。这让测试更可重复，也帮助我们分类常见错误。

现在尝试测试更复杂的 alphabetRot 封闭性：

代码清单 9.16 alphabetRot 封闭性的 QuickCheck 属性

prop_alphabetRotClosed :: Alphabet -> Int -> Char -> Bool
prop_alphabetRotClosed alphabet n c =
  let c' = alphabetRot alphabet n c      -- #1
   in c' `elem` alphabet                 -- #1

快速检查：

ghci> quickCheck prop_alphabetRotClosed
*** Failed! Falsified (after 1 test and 1 shrink):
""
0
'a'

这里有两点值得注意。首先，QuickCheck 可以为三参数函数生成输入，任意数量参数都会独立生成。第二，我们的属性错了！失败输入显示 alphabet 是空字符串，而 c 需要是 alphabet 的元素，且 alphabet 不应为空。该如何解决？

在自制框架中，我们通过修改随机值生成器来只生成正确值。现在也需要在 QuickCheck 中这样做。

9.4 为测试生成随机值（Generating random values for testing）

随机值生成是 QuickCheck 的核心，因为没有它，属性测试就没有意义。QuickCheck 能根据类型自动推断正确生成器，这是如何实现的？

答案是 Arbitrary 类型类：

ghci> :i Arbitrary
type Arbitrary :: * -> Constraint
class Arbitrary a where
  arbitrary :: Gen a
  shrink :: a -> [a]
  {-# MINIMAL arbitrary #-}

它定义了 arbitrary，用于生成随机值；还定义了 shrink，稍后讨论。最小定义只需要 arbitrary，因此暂时可以忽略 shrink。

9.4.1 Gen 随机值函数（The random generator Gen random value function）

Gen 与我们的 RandomIO 很相似。它定义如何为特定类型生成随机值。可以用 generate 在 IO 动作中从 Gen 生成随机值：

ghci> generate arbitrary :: IO Int
15
ghci> generate arbitrary :: IO [Bool]
[True,True,True,False,True,False]
ghci> generate arbitrary :: IO (Maybe Float)
Just (-9.993277)
ghci> generate arbitrary :: IO (Either String Char)
Right '.'

QuickCheck 还提供许多辅助函数：

• choose :: Random a => (a, a) -> Gen a：在区间中生成数值
• chooseAny :: Random a => Gen a：把 Random 实例的随机值转换为 Gen
• oneof :: [Gen a] -> Gen a：随机选择一个生成器
• elements :: [a] -> Gen a：从给定列表中随机选择元素
• suchThat :: Gen a -> (a -> Bool) -> Gen a：根据谓词跳过不需要的元素
• listOf :: Gen a -> Gen [a]：从生成器生成随机长度列表
• listOf1 :: Gen a -> Gen [a]：类似 listOf，但不生成空列表
• vectorOf :: Int -> Gen a -> Gen [a]：生成给定长度列表
• vector :: Arbitrary a => Int -> Gen [a]：类似 vectorOf，但生成器由类型推断
• shuffle :: [a] -> Gen [a]：生成给定列表的随机排列
• sublistOf :: [a] -> Gen [a]：生成给定列表的随机子列表

练习：生成器组合子

我们已经在 SimpleCheck 中实现了 suchThat。现在可以复制 QuickCheck 的更多函数，感受它如何计算测试值。保持类型签名一致，只是用 RandomIO 替代 Gen，并尽量让性能更好。

定义生成器与定义 RandomIO 很相似。可以使用熟悉的 do 记法。下面重建之前用于字母表属性的生成器。

代码清单 9.17 alphabetRot 测试数据的 QuickCheck 生成器

gen :: Gen (Alphabet, Int, Char)
gen = do
  size <- getSize                                      -- #1
  alphabet <- arbitrary `suchThat` (not . null)        -- #2
  n <- choose (-size, size)                            -- #3
  c <- elements alphabet                               -- #4
  return (alphabet, n, c)                              -- #5

getSize 返回 QuickCheck 生成器的内部大小。这个大小决定生成值的一些参数。例如，Int 的标准生成器会产生绝对值受内部大小影响的值。默认大小为 30，但可以用 resize 修改。

当想在某个属性上使用特定生成器时，可以用 forAll。它显式设置测试用例生成器，并返回一个属性。

代码清单 9.18 描述字母表函数封闭性的属性

prop_alphabetRotClosed :: Property
prop_alphabetRotClosed =
  forAll gen prop                                      -- #1
  where
    prop :: (Alphabet, Int, Char) -> Bool
    prop (alphabet, n, c) =
      let c' = alphabetRot alphabet n c                -- #2
       in c' `elem` alphabet

    gen :: Gen (Alphabet, Int, Char)
    gen = do
      size <- getSize                                  -- #3
      alphabet <- arbitrary `suchThat` (not . null)    -- #4
      n <- choose (-size, size)                        -- #5
      c <- elements alphabet                           -- #6
      return (L.nub alphabet, n, c)                    -- #7

这段实现应放在新模块中，避免与之前实现冲突。它与旧代码相似，但测试表达能力更强。

9.4.2 示例：AssocMap

回想第 5 章引入的 AssocMap 类型。现在希望测试它，但首先需要能随机生成这种类型的值。Arbitrary 类型类正是为此而生。

代码清单 9.19 第 5 章中的 AssocMap 定义

newtype AssocMap k v = AssocMap [(k, v)]
  deriving (Show)

每个键只能出现一次，因此任意生成该类型值时必须遵守这个属性。Gen 有 Functor 实例，因此可以用 fmap 和 <$> 修改生成值。我们可以生成无重复键列表，再生成同样数量的值，并把二者组合成映射。

代码清单 9.20 关联映射的 QuickCheck 生成器

import qualified Data.List as L             -- #1
import Test.QuickCheck                      -- #2

genAssocMap :: (Eq k, Arbitrary k, Arbitrary v) => Gen (AssocMap k v)
genAssocMap = do
  keys <- L.nub <$> arbitrary               -- #2
  vals <- vectorOf (L.length keys) arbitrary -- #3
  return $ AssocMap (L.zip keys vals)        -- #4

约束很重要：键和值都需要 Arbitrary 实例。使用 arbitrary 可以让生成器适用于任意已有生成器的类型。

ghci> generate genAssocMap :: IO (AssocMap Int Bool)
AssocMap [(0,True),(-1,False),...]
ghci> generate genAssocMap :: IO (AssocMap Bool [Float])
AssocMap [(True,[7.29,17.28,...])]

这完成了 Arbitrary 实例的第一块拼图。第二部分 shrink 也不应忽略。

9.4.3 测试用例缩减（Shrinking test cases）

测试失败时，我们通常不关心复杂反例，而希望得到最小、更容易理解的反例。QuickCheck 内置 shrinking，会尝试缩小已发现的反例，并重新检查它是否仍然失败。这个过程重复到不能继续缩小为止。图 9.2 展示了 QuickCheck、属性和 shrinking 的关系。

图 9.2 QuickCheck、属性和 shrinking 的相互作用

对 QuickCheck 知道如何生成随机数据的每种类型，它也知道是否以及如何缩小该类型的值。这来自 Arbitrary 类型类中的 shrink 函数。其类型 a -> [a] 表明：它是一个纯函数，从输入生成一组缩小候选值。因此它的输出只依赖输入，是确定性的。这也是 QuickCheck 生成的反例有时看起来确定的原因。

ghci> shrink 'H'
"abchABC"
ghci> shrink 'A'
"abc"
ghci> shrink '\n'
"abcABC123 "

shrink 不应把输入本身作为缩小值返回，否则 shrinking 可能陷入无限循环。

如何缩小 AssocMap？如果键和值类型都有 Arbitrary 实例，那么它们的元组以及元组列表也有实例。因此可以缩小 AssocMap 内部列表，但必须小心：shrink 可能改变值，从而破坏“键不重复”的不变量。因此 shrink 时要确保键只出现一次。

代码清单 9.21 关联映射的 shrink 函数

shrinkAssocMap ::
  (Eq k, Arbitrary k, Arbitrary v) =>
  AssocMap k v ->
  [AssocMap k v]
shrinkAssocMap (AssocMap xs) =
  L.map
    (AssocMap . L.nubBy (\(k1, _) (k2, _) -> k1 == k2))
    (shrink xs)                              -- #2

这能让失败的 AssocMap 反例更简单。最后一步是用这些函数构造 Arbitrary (AssocMap k v) 实例。

代码清单 9.22 AssocMap 的 Arbitrary 实例

instance (Eq k, Arbitrary k, Arbitrary v) => Arbitrary (AssocMap k v)
  where
    arbitrary = genAssocMap                  -- #1
    shrink = shrinkAssocMap                  -- #2

现在可以在属性中自由生成 AssocMap 随机值，也可以在更大的生成器中使用它。

练习：关联列表属性

既然已经为 AssocMap 实现了 Arbitrary 实例，请为该类型编写可测试属性。需要检查它作为映射的基本功能：

• 插入后可以查找到值。
• 同一个键多次插入会覆盖已有值。
• 删除键按预期工作。
• empty 确实为空。
• 修改映射不会破坏不变量。

可以继续思考更多属性，并用 QuickCheck 测试它们。

9.5 属性测试的实际使用（Practical usage of property testing）

到目前为止，我们已经学习了 QuickCheck 中的不同概念：属性如何测试、随机值如何生成。现在关注如何用这个库测试代码，以及设计测试时要注意什么。

先回到排序函数测试：

ghci> quickCheck $ sorts sort
+++ OK, passed 100 tests.
ghci> quickCheck $ sorts id
+++ OK, passed 100 tests.

等等，id 不可能排序列表。我们需要调查。

9.5.1 冗余与覆盖报告（Verbosity and coverage reports）

可以用一些修改器改变属性测试执行方式。第一个是 verbose，它会详细打印测试用例：

ghci> quickCheck . verbose $ sorts sort
Passed:
[]
Passed:
[()]
...
+++ OK, passed 100 tests.

这已经不对劲了。被测列表是 unit 类型！显然，只包含这个类型的任何列表都是平凡有序的，因为它只有一个值。需要显式说明 QuickCheck 应使用的测试类型。

注意 这里发生的是类型默认化。在某些情况下，如果 GHC 不清楚类型应如何解析，就会自动默认到某种类型。这里列表元素类型默认成了 ()。

可以给属性显式命名并添加类型签名：

ghci> :{
ghci| prop_sortSorts :: [Int] -> Bool
ghci| prop_sortSorts xs = sort `sorts` xs
ghci| :}
ghci> quickCheck . verbose $ prop_sortSorts
Passed:
[]
Passed:
[0,3]
Passed:
[4,-3]
...
+++ OK, passed 100 tests.

现在值看起来合理了。不过，QuickCheck 会逐步增加生成器大小，因此测试开头会多次测试空列表。要了解测试数据，可以用 collect 收集某个统计值。例如检查有多少用例为空：

ghci> :{
ghci| prop_sortSorts :: [Int] -> Property
ghci| prop_sortSorts xs = collect (null xs) $ sort `sorts` xs
ghci| :}
ghci> quickCheck prop_sortSorts
+++ OK, passed 100 tests:
95% False
 5% True

也可以用 label 给统计分类命名：

ghci> :{
ghci| prop_sortSorts :: [Int] -> Property
ghci| prop_sortSorts xs = label (if null xs then "empty" else "not empty") $
ghci|   sort `sorts` xs
ghci| :}
ghci> quickCheck prop_sortSorts
+++ OK, passed 100 tests:
95% not empty
 5% empty

注意，这时属性类型从 [Int] -> Bool 变成了 [Int] -> Property，因为 collect 和 label 都会产生 Property。

如果想测试至少有两个元素的列表，可以使用前置条件。QuickCheck 中通过 ==> 添加：

ghci> :{
ghci| prop_sortSorts :: [Int] -> Property
ghci| prop_sortSorts xs = length xs >= 2 ==> sort `sorts` xs
ghci| :}
ghci> quickCheck prop_sortSorts
+++ OK, passed 100 tests; 43 discarded.

被丢弃的测试用例不满足前置条件。前置条件适合绝对排除不符合规格的用例。如果只是想观察覆盖率，应使用 cover：

ghci> :{
ghci| prop_sortSorts :: [Int] -> Property
ghci| prop_sortSorts xs = cover 25 (length xs >= 2) "non-trivial" $
ghci|   sort `sorts` xs
ghci| :}
ghci> quickCheck prop_sortSorts
+++ OK, passed 100 tests (93% non-trivial).

cover 接收三个参数：0 到 100 的最小通过比例、判断条件，以及标签。它会统计满足条件的测试用例比例。

注意 cover 不会让属性测试失败，只会在覆盖率不足时警告。如果希望失败，可以用 checkCoverage 包装属性。

9.5.2 修改测试参数（Modifying a test's parameters）

QuickCheck 提供许多修改测试行为的函数：

• verbose：让测试输出更详细，也可使用辅助函数 verboseCheck
• verboseShrinking：在输出中包含 shrinking 过程
• noShrinking：禁用属性的 shrinking
• withMaxSuccess：配置成功多少次后测试完成，默认是 100
• within：如果属性测试未在指定微秒内完成，则失败

withMaxSuccess 和 within 对测试尤其重要。有时 100 个测试用例不够；有时又需要确保时间敏感代码能及时执行。不过具体设置高度依赖测试用例。

9.5.3 构建测试套件（Constructing test suites）

用 stack new 初始化项目时，Stack 不只创建库和可执行文件结构，还会在 test 子目录中创建 Spec.hs。这个子结构用于测试库和可执行文件。测试套件可以通过 stack test 执行。Stack 如何知道测试失败？默认情况下，由以 Spec.hs 作为主模块编译出的程序退出码决定。

一个简单模板如下。

代码清单 9.23 Stack 测试套件模板

module Main where

import System.Exit (exitFailure, exitSuccess) -- #1

main :: IO ()
main = do
  success <- ...
  if success                                  -- #2
    then exitSuccess
    else exitFailure

QuickCheck 提供 quickCheckAll，它会收集模块中所有属性并对它们运行 quickCheck。这是通过 Template Haskell 和属性命名约定完成的。

Template Haskell 是 GHC 扩展，允许使用元编程并直接操作程序抽象语法树。QuickCheck 用它枚举模块中所有带 prop_ 前缀的属性，并自动调用 quickCheck。这样，模块可以定义一组属性，并提供运行所有测试的动作。

假设在 Spec.hs 旁边创建两个测试套件模块 SuiteOne.hs 和 SuiteTwo.hs。它们都导出 runTests，并用 Template Haskell 收集模块中的属性。

代码清单 9.24 测试套件示例

{-# LANGUAGE TemplateHaskell #-}        -- #1

module SuiteOne where

import Test.QuickCheck

prop_true :: Int -> Bool                -- #2
prop_true = const True

prop_false :: Int -> Bool               -- #3
prop_false = const False

return []                               -- #4

runTests :: IO Bool
runTests = $quickCheckAll               -- #5

需要启用 TemplateHaskell 扩展。quickCheckAll 前面的美元符号是 Template Haskell 的特殊语法。代码中的 return [] 是当前推荐的变通方案，用于处理模板相关问题。

另一个测试套件可以包含更复杂的属性：

代码清单 9.25 另一个测试套件示例

{-# LANGUAGE TemplateHaskell #-}        -- #1

module SuiteTwo where

import Test.QuickCheck

prop_addPos :: Int -> Int -> Property   -- #2
prop_addPos x y =
  withMaxSuccess 500 $
    x > 0 && y > 0 ==> x + y > 0

prop_multZero :: Int -> Property        -- #3
prop_multZero x =
  noShrinking $
    cover 95 (x /= 0) "non-zero" $ x * 0 == 0

return []                               -- #4

runTests :: IO Bool
runTests = $quickCheckAll               -- #5

属性数量可以有几百个，也无需手写检查调用。扩展测试套件时，只要再写一个属性，下次运行 stack test 时它就会自动检查。

代码清单 9.26 使用测试套件的主模块示例

module Main where

import qualified SuiteOne as S1          -- #1
import qualified SuiteTwo as S2          -- #1
import System.Exit (exitFailure, exitSuccess) -- #2

main :: IO ()
main = do
  s1success <- S1.runTests               -- #3
  s2success <- S2.runTests               -- #3
  if s1success && s2success              -- #4
    then exitSuccess
    else exitFailure

runTests 返回一个布尔值，说明测试是否失败。更重要的是，运行时也会产生输出。因此测试运行顺序有意义，希望先出现的测试应先在 main 中执行。

练习：短路测试

当前实现没有短路逻辑。如果一个套件失败，仍然会继续测试所有属性，然后再决定测试是否成功。开发时可能不希望这样。请添加一个测试参数，用于启用或禁用测试套件失败时的快速失败。

可以通过 --test-arguments 向测试传参：

shell $ stack test --test-arguments "--my-cool-flag"

执行测试示例：

shell $ stack test
properties> test (suite: properties-test)
=== prop_true from test/SuiteOne.hs:7 ===
+++ OK, passed 100 tests.
=== prop_false from test/SuiteOne.hs:10 ===
*** Failed! Falsified (after 1 test):
0
=== prop_addPos from test/SuiteTwo.hs:7 ===
+++ OK, passed 500 tests; 1758 discarded.
=== prop_multZero from test/SuiteTwo.hs:12 ===
+++ OK, passed 100 tests (97% non-zero).
properties> Test suite properties-test failed

这是一种比较朴素的测试方式。也可以从 package.yaml 创建更多测试套件，或者使用 Tasty 这样的库，把 QuickCheck、SmallCheck 和手工单元测试组合成更丰富的测试套件。对小项目来说，我们的方法已经足够。

练习：项目测试套件

现在我们知道了如何把测试套件整合到项目中，请为之前的项目添加测试套件。为各种场景思考合适属性，验证一切按预期工作。这里没有绝对对错，发挥创造力，为自己的类型创建 Arbitrary 实例，并看看能想出哪些属性。

还需要提到，Haskell 中还存在其他测试框架，例如与 QuickCheck 类似的 Hedgehog，以及更关注基于示例单元测试的 HUnit。每个框架都有自己的能力，根据项目规模和功能，你可能会偏好其中某个。

9.5.4 测试有效性（The effectiveness of testing）

虽然已经介绍了 Haskell 纯函数在可测试性上的好处，最后仍值得多讨论一点。为什么要为软件编写测试？我们试图实现什么？最明显的目标是正确性：希望程序根据某些规格产生结果。例如，素数生成器显然应该只产生素数。不过，也希望这些属性不会随着时间改变。重构代码后，软件仍应通过所有测试套件。

这给程序带来信心。可以确信它们产生正确结果，也可以放心修改代码而不引入回归。如果说 Haskell 有一个主要优势，那正是信心。静态类型、纯函数以及副作用与无副作用编程的清晰分离，让 Haskell 不仅非常适合测试，也让这些测试有效。

由于纯函数没有副作用，它们只是数据上的转换。对这些转换的属性测试必须确保相关属性成立：如果输入数据满足某些属性，输出也应满足某些属性。本章中，我们看到如何实现这些测试：

• 使用前置条件或专门构造的生成器确保输入数据属性。
• 在转换结果上检查想要保证的属性。
• 函数通过正确结果进行测试。
• 数据类型通过正确构造以及转换期间的不变量进行测试。
• 将属性打包成测试套件，以在模块内部或整个系统范围内获得信心。

其他语言也能编写测试，但很少能像纯函数式代码那样，用相对少量测试获得如此高的信心。纯函数代码中的属性测试类似形式化验证：它使用形式化属性，而不是简单观察程序行为。这让软件更容易重构、扩展和扩大规模。在持续集成和持续交付等实践中，这些测试是成功运行的骨架，也经常能避免灾难性回归。

总结

• 纯函数中的随机值要求随机值生成器作为参数，并成为返回值的一部分。
• 可以在 IO 动作中使用 AtomicGenM 和 globalStdGen 访问全局随机值生成器。
• Random 和 Uniform 类型类提供了许多可随机生成的类型。
• 属性测试使用形式化特征和随机输入查找实现中的错误。
• 随机生成器应当可组合，这样更容易编写。
• QuickCheck 通过类型系统和类型类自动选择随机值生成器。
• Arbitrary 类型类不仅为类型提供随机值生成器，也提供把值缩小为更小或更简单值的函数。
• QuickCheck 的生成器使用内部大小来创建不同复杂度的随机值。
• quickCheckAll 可用于自动收集模块中的属性并执行检查。
• 纯函数式代码中的属性测试可以确保数据类型、函数和模块上的形式化属性。