Scala函数式编程：8 基于属性的测试

本章涵盖

• 验证 API 的属性
• 开发基于属性的测试库

在第7章中，我们设计了一个用于表达并行计算的函数库。在那里，我们介绍了 API 应该形成代数的想法，即数据类型、基于这些数据类型的函数以及表达这些函数之间关系的定律或属性的集合。我们还暗示了这样一种想法，即有可能以某种方式自动检查这些法律。

本章将带我们进入一个简单但功能强大的基于属性的测试库。这种库的一般思想是将程序行为规范与测试用例的创建分离。程序员专注于指定程序的行为并对测试用例给出高级约束;然后，框架自动生成满足这些约束的测试用例，并运行测试以确保程序按指定运行。

尽管用于测试的库与用于并行计算的库具有非常不同的目的，但我们会发现这些库具有许多令人惊讶的相似组合器。我们将在第 3 部分中回到这种相似性。

例如，在 ScalaCheck （http://mng.bz/n2j9）（一个基于 Scala 属性的测试库）中，属性类似于下面的列表。

清单 8.1 Scala检查属性

import org.scalacheck.{Gen, Prop} val intList = Gen.listOf(Gen.choose(0, 100)) ① val prop = ② Prop.forAll(intList)(ns => ns.reverse.reverse == ns) && ③ Prop.forAll(intList)(ns => ns.headOption == ns.reverse.lastOption) ④ val failingProp = Prop.forAll(intList)(ns => ns.reverse == ns) ⑤

（0） 100 到 <> 之间的整数列表的生成器

（2） 指定 List.reverse 方法行为的属性

（3） 检查两次反转列表是否返回原始列表。

（4）检查反转后的第一个元素是否成为最后一个元素。

（5） 明显虚假的财产

我们可以按如下方式检查属性：

scala> prop.check OK, passed 100 tests. scala> failingProp.check ! Falsified after 6 passed tests. > ARG_0: List(0, 1)

在这里，intList 不是一个 List[Int]，而是一个 Gen[List[Int]]，它是知道如何生成 List[Int] 类型的测试数据的东西。我们可以从这个生成器中采样，它将生成不同长度的列表，填充 0 到 100 之间的随机数。基于属性的测试库中的生成器具有丰富的 API。我们可以以不同的方式组合和组合生成器，重用它们，等等。

函数 Prop.forAll 通过将 Gen[A] 类型的生成器与类型 A => 布尔值的某个谓词组合来创建属性。该属性断言生成器生成的所有值都应满足谓词。图 8.1 显示了 intList 生成器与使用它的属性之一之间的关系。与生成器一样，属性也可以具有丰富的 API。在这个简单的示例中，我们使用 && 来组合两个属性。仅当任何生成的测试用例都无法伪造这两个属性时，生成的属性才会成立。这两个属性共同构成了反向方法正确行为的部分规范。1

图8.1 生成器和属性

当我们调用 prop.check 时，ScalaCheck 将随机生成 List[Int] 值，以尝试找到伪造我们提供的谓词的情况。输出表明 ScalaCheck 已经生成了 100 个测试用例（类型为 List[Int]），并且它们都满足谓词。当然，属性可能会失败;failingProp.check 的输出指示谓词对某些输入进行了 false 测试，这有助于打印出来以方便进一步的测试或调试。

要习惯于以这种方式考虑测试，请提出指定总和实现的属性：List[Int] => Int 函数。您不必将属性写成可执行的 ScalaCheck 代码 - 非正式描述很好。以下是一些帮助您入门的想法：

• 反转列表并求和应提供与对原始非反转列表求和相同的结果。
• 如果列表中的所有元素都具有相同的值，则总和应该是多少？
• 你能想到其他属性吗？

哪些属性指定查找 List[Int] 最大值的函数？

基于属性的测试库通常配备其他有用的功能。稍后我们将详细讨论其中的一些功能，但以下内容应提供可能的功能：

• 测试用例最小化 - 如果测试失败，框架会尝试较小的大小，直到找到同样失败的最小测试用例，这对于调试目的更具启发性。例如，如果属性对于大小为 10 的列表失败，则框架会尝试较小的列表，并报告未通过测试的最小列表。
• 详尽的测试用例生成 - 我们将某些 Gen[A] 可能生成的值集称为域。2 当域足够小时（例如，如果它都是小于 100 的偶数整数），我们可以详尽地测试它的所有值，而不是生成样本值。如果该属性适用于域中的所有值，那么我们就有了实际的证据，而不仅仅是缺乏相反的证据。

ScalaCheck 只是一个基于属性的测试库，我们将在本章中从头开始派生我们自己的库。就像第7章一样，这主要是出于教学目的，但也部分是因为我们应该认为没有图书馆是任何主题的最终决定。使用现有的库（如 ScalaCheck）当然没有错，现有库可以是一个很好的想法来源。但是，即使您决定喜欢现有库的解决方案，花一两个小时玩设计并写下一些类型签名也是了解有关该领域的更多信息并了解设计权衡的好方法。

本节将是发现我们库的数据类型和函数的另一个混乱和迭代过程。这一次，我们正在设计一个用于基于属性的测试的库。和以前一样，这是一个窥视可能设计的人的机会。

我们走的特定路径和我们到达的图书馆不一定与您自己想出的相同。如果您不熟悉基于属性的测试，那就更好了;这是一个探索新领域及其设计空间并对其做出自己发现的机会。如果您在任何时候对如何设计这样的库感到灵感或有自己的想法，请不要等待练习提示您;放下书，去玩你的想法。如果您没有想法或遇到困难，您可以随时回到该章节。

话虽如此，让我们开始吧。我们应该为测试库使用哪些数据类型？我们应该定义哪些基元，它们可能意味着什么？我们的功能应该满足哪些法律？和以前一样，我们可以看一个简单的例子，读出所需的数据类型和函数，看看我们发现了什么。为了获得灵感，让我们看一下我们之前展示的 ScalaCheck 示例：

val intList = Gen.listOf(Gen.choose(0, 100)) val prop = Prop.forAll(intList)(ns => ns.reverse.reverse == ns) && Prop.forAll(intList)(ns => ns.headOption == ns.reverse.lastOption)

在不知道Gen.select或Gen.listOf的实现的情况下，我们可以猜测它们返回的任何数据类型（我们称之为Gen - 生成器的缩写）在某种类型中必须是参数化的。也就是说，Gen.choose（0， 100） 可能返回一个 Gen[Int]，而 Gen.listOf 是一个签名为 Gen[Int] => Gen[List[Int]] 的函数。但是由于 Gen.listOf 似乎不应该关心它作为输入接收的 Gen 的类型（需要单独的组合器来创建 Int 、Double 、String 等列表会很奇怪），让我们让它成为多态的：

def listOf[A](a: Gen[A]): Gen[List[A]]

通过查看此签名，我们可以学到很多东西。请注意我们未指定的内容 - 要生成的列表的大小。为了实现这一点，我们的生成器必须假设或被告知大小。假设大小似乎有点不灵活，因为任何假设都不太可能在所有上下文中都适用。因此，似乎必须告诉生成器要生成的测试用例的大小。我们可以想象一个 API 来明确这一点：

def listOfN[A](n: Int, a: Gen[A]): Gen[List[A]]

这当然是一个有用的组合器，但不必显式指定大小也很强大。这意味着无论运行测试什么函数都可以自由选择测试用例大小，这为我们前面提到的测试用例最小化提供了可能性。如果大小始终由程序员固定和指定，则测试运行程序将不具有这种灵活性。当我们在设计中走得更远时，请记住这一点。

这个例子的其余部分呢？Prop.forAll 函数看起来很有趣;我们可以看到它接受一个Gen[List[Int]]和一个看起来是相应的谓词：List[Int] =>布尔值。但同样，似乎 forAll 不应该关心生成器和谓词的类型，只要它们匹配即可。我们可以用以下类型来表达这一点：

def forAll[A](a: Gen[A])(f: A => Boolean): Prop

在这里，我们简单地发明了一种新的类型，Prop（属性的缩写，在ScalaCheck命名之后），用于将Gen绑定到谓词的结果。我们可能不知道 Prop 的内部表示或它支持的其他功能，但基于这个例子，我们可以看到它有一个 && 运算符，所以让我们介绍一下：

trait Prop: def &&(that: Prop): Prop8.1.3 属性的含义和接口

现在我们有了 API 的一些片段，让我们讨论一下我们希望我们的类型和函数意味着什么。首先考虑道具。我们知道存在All（用于创建属性），&&（用于组合属性）和check（用于运行属性）的函数。在 ScalaCheck 中，此检查方法具有打印到控制台的副作用。将其公开为方便功能是可以的，但它不是组合的基础。例如，如果 Prop 的表示只是检查方法，我们就无法实现 &&3

trait Prop: def check: Unit def &&(that: Prop): Prop = ???

由于检查有副作用，在这种情况下，实现&&的唯一选择是对两个Prop值运行检查方法。因此，如果 check 打印出一份测试报告，那么我们将得到其中两个，它们将相互独立地打印失败和成功。这可能不是一个正确的实现;问题不在于检查有副作用，而更普遍的是，它丢弃了信息。

要使用 && 这样的组合器组合 Prop 值，我们需要检查（或任何运行属性的函数）以返回一些有意义的值。该值应具有什么类型？让我们考虑一下我们希望从检查我们的属性中获得什么样的信息。至少，我们需要知道属性是成功还是失败，这让我们可以实现 &&.

假设 Prop 的以下表示形式，实现 && 作为 Prop 的方法：

trait Prop: def check: Boolean

在这个表示中，Prop 等价于4 的非严格布尔值，任何通常的布尔函数（AND、OR、NOT、XOR 等）都可以为 Prop 定义——但仅靠布尔值可能是不够的。如果一个属性失败，我们可能想知道有多少个测试首先成功，哪些参数导致了失败，如果一个属性成功，知道它运行了多少个测试会很有用。让我们尝试返回 要么 来指示成功或失败：

object Prop: opaque type SuccessCount = Int ① ... trait Prop: def check: Either[???, SuccessCount]

（1） 像这样的不透明类型别名可以提高 API 的可读性和类型安全性。

在失败的情况下，我们应该返回什么类型？我们对生成的测试用例类型一无所知。我们应该在 Prop 中添加一个类型参数并使其成为 Prop[A] 吗？然后检查可以返回 [A，Int] 。在走得太远之前，让我们问问自己，我们是否真的关心导致属性失败的值的类型。我们真的没有;如果我们要对故障进行进一步计算，我们只会关心类型。很可能我们最终会将其打印到屏幕上，供运行测试的人员进行检查。毕竟，这里的目标是找到错误并向某人指出哪些测试用例触发了这些错误，以便他们可以修复它们。作为一般规则，我们不应该使用 String 来表示我们想要计算的数据。但是对于价值观，我们只是要向人类展示字符串是绝对合适的。这表明我们可以摆脱 Prop 的以下表示：

object Prop: opaque type FailedCase = String opaque type SuccessCount = Int trait Prop: def check: Either[(FailedCase, SuccessCount), SuccessCount]

如果失败，check 将返回一个 Left（（s， n）） ，其中 s 是表示导致属性失败的值的某个字符串，n 是在失败发生之前成功的事例数。这负责检查的返回值 - 至少目前 - 但是要检查的参数呢？现在，检查方法不接受任何参数。这就够了吗？我们可以考虑 Prop 可以访问哪些信息，只需检查 Prop 值的创建方式即可。特别是，让我们看看所有：

def forAll[A](a: Gen[A])(f: A => Boolean): Prop

如果不了解Gen的表示，很难说这里是否有足够的信息来生成A类型的值（这是我们需要实现的检查）。因此，现在，让我们将注意力转向Gen，以更好地了解它的含义及其依赖项可能是什么。

我们之前确定 Gen[A] 是知道如何生成类型 A 的值的东西。它有什么方法可以做到这一点？好吧，它可以随机生成这些值。回顾第6章的例子;在该章中，我们为纯函数随机数生成器RNG提供了一个接口，并展示了如何方便地组合使用它的计算。我们可以使 Gen 成为一种类型，它将状态转换包装在随机数生成器上：5

opaque type Gen[ A] = State[RNG, A]

使用Gen的这种表示实现Gen.choice。它应该在开始停止排他性的范围内生成整数。随意使用您已经编写的函数：

def choose(start: Int, stopExclusive: Int): Gen[Int]

让我们看看我们还可以使用 Gen 的这种表示来实现什么。尝试实现单元、布尔值和 listOfN 。

def unit[A](a: => A): Gen[A] ① def boolean: Gen[Boolean] extension [A](self: Gen[A]) def listOfN[A](n: Int): Gen[List[A]] ②

（1） 始终生成值 a

（2） 使用生成器 g 生成长度为 n 的列表

正如我们在第7章中所讨论的，我们有兴趣了解哪些操作是基元的，哪些操作是派生的，以及找到一个小而富有表现力的基元集。探索一组给定基元可表达内容的一个好方法是选择一些你想要表达的具体示例，看看你是否可以组装你想要的功能。在执行此操作时，请查找模式，尝试将这些模式分解到组合器中，并优化您的基元集。我们鼓励您停止阅读这里，而只是使用我们到目前为止编写的基元和组合器。如果你想要一些具体的例子来激励你，这里有一些想法：

• 如果我们可以在某个范围内生成单个 Int，我们是否需要一个新的原语来生成某个范围内的（Int、Int）对？
• 我们可以从世代[A]中产生一个世代[选项[A]]吗？来自世代[选项[A]]的世代[A]呢？
• 我们可以使用现有的原语以某种方式生成字符串吗？

游戏的重要性

您不必等待一个具体的例子来强制探索设计空间。事实上，如果您完全依赖具体的、明显有用的或重要的示例来设计您的 API，那么您通常会错过设计空间的各个方面，并生成具有临时、过于具体的功能的 API。我们不想将我们的设计过度适合我们现在碰巧想到的例子。我们希望将问题简化为本质，有时最好的方法是玩耍。不要试图解决重要问题或产生有用的功能 - 不是马上。只需尝试不同的表示、基元和操作;让问题自然出现;并探索任何激起您好奇心的东西。（您可能会认为，这两个函数看起来很相似。我想知道里面是否隐藏着一些更一般的操作;使这种数据类型多态有意义吗？或者将表示的这一方面从单个值更改为值列表意味着什么？这样做没有对错之分，但是有许多不同的设计选择，不可能不一头扎进迷人的问题中去玩。从哪里开始并不重要——如果你继续玩这个领域，它将无情地指导你做出所有所需的设计选择。

假设我们想要一个生成对的 Gen[（字符串，字符串）]，其中第二个字符串仅包含第一个字符串中的字符。或者假设我们有一个Gen[Int]，它选择一个介于0和11之间的整数，我们想创建一个Gen[List[Double]]，然后生成所选长度的列表。在这两种情况下，都有一个依赖关系：我们生成一个值，然后使用该值来确定下一步要使用的生成器。为此，我们需要 flatMap ，它允许一个生成器依赖于另一个生成器。

实现 flatMap ，然后使用它来实现这个更动态的 listOfN 版本。将 flatMap 和 listOfN 放在 Gen 类中：

extension [A](self: Gen[A]) def flatMap[B](f: A => Gen[B]): Gen[B] extension [A](self: Gen[A]) def listOfN(size: Gen[Int]): Gen[List[A]]

实现联合，用于将两个相同类型的生成器合并为一个，方法是从每个生成器中提取具有相等可能性的值：

def union[A](g1: Gen[A], g2: Gen[A]): Gen[A]

实现加权，一个联合版本，它接受每个世代的权重，并从每个世代生成与其权重成正比的概率值：

def weighted[A](g1: (Gen[A], Double), g2: (Gen[A], Double)): Gen[A]

现在我们对生成器的表示有了更多的了解，让我们回到我们对 Prop 的定义。我们的Gen表示已经揭示了有关Prop要求的信息，我们目前对Prop的定义如下所示：

trait Prop: def check: Either[(FailedCase, SuccessCount), SuccessCount]

Prop 相当于6 非严格 要么 ，但它缺少一些信息。我们在 SuccessCount 中有成功的测试用例的数量，但我们没有指定在考虑属性已通过测试之前要检查的测试用例数量。我们当然可以硬编码一些东西，但最好抽象出这个依赖关系：

opaque type TestCases = Int object TestCases: extension (x: TestCases) def toInt: Int = x def fromInt(x: Int): TestCases = x opaque type Prop = TestCases => Either[(FailedCase, SuccessCount), SuccessCount]

此外，我们正在记录双方的成功测试数量。但是当一个属性通过时，它暗示通过的测试数将等于要检查的参数，因此检查的调用方不会通过被告知成功计数来学习任何新东西。由于我们目前也不需要任何信息，我们可以将其转换为选项：

opaque type Prop = TestCases => Option[(FailedCase, SuccessCount)]

这似乎有点奇怪，因为 None 表示所有测试都成功并且属性已通过，而 Some 将表示失败。到目前为止，我们只使用“选项”的“无”情况来指示失败，但在本例中，我们使用它来表示没有失败。这是选项的一个完全合法的用途，但它的意图不是很清楚。因此，让我们创建一个新的数据类型，相当于 Option[（FailedCase， SuccessCount）]，它非常清楚地显示了我们的意图。

示例 8.2 创建结果数据类型

enum Result: case Passed ① case Falsified( failure: FailedCase, successes: SuccessCount) ② def isFalsified: Boolean = this match case Passed => false case Falsified(_, _) => true

（1） 表示所有测试通过的行×

（2） 表示其中一个测试用例伪造了属性

现在这足以代表道具吗？让我们再来看看 forAll .能实施吗？为什么，或者为什么不呢？

def forAll[A](a: Gen[A])(f: A => Boolean): Prop

我们可以看到 forAll 没有足够的信息来返回 道具 .除了要尝试的测试用例数量外，运行 Prop 还必须具有生成测试用例所需的所有信息。如果它需要使用我们当前的Gen表示来生成随机测试用例，它将需要一个RNG。让我们将该依赖项传播到 Prop：

opaque type Prop = (TestCases, RNG) => Result

如果我们考虑它可能需要的其他依赖项，除了测试用例的数量和随机性的来源之外，我们可以将这些作为额外的参数添加以供以后检查。

我们现在有足够的信息来实施 所有人 .下面的清单显示了一个简单的实现。

示例 8.3 实现 for All

def forAll[A](as: Gen[A])(f: A => Boolean): Prop = (n, rng) => randomLazyList(as)(rng) .zip(LazyList.from(0)) .take(n) .map: ① case (a, i) => try if f(a) then Passed else Falsified(a.toString, i) ② catch case e: Exception => Falsified(buildMsg(a, e), i) ③ .find(_.isFalsified) .getOrElse(Passed) } def randomLazyList[A](g: Gen[A])(rng: RNG): LazyList[A] = LazyList.unfold(rng)(rng => Some(g.run(rng))) ④ def buildMsg[A](s: A, e: Exception): String = s"test case: $s\n" ⑤ s"generated an exception: ${e.getMessage}\n" s"stack trace:\n ${e.getStackTrace.mkString("\n")}"

（1） 一个惰性对列表，（a， i），其中 a 是随机值，i 是它在列表中的索引

（2） 当测试失败时，记录失败的案例及其索引，以便我们知道在测试之前成功了多少次。

（3） 如果测试用例生成异常，请将其记录在结果中。

（4） 这通过重复采样生成器生成 A 值的无限惰性列表。回想一下，在状态上运行会评估状态操作。

（5） 这是字符串插值语法。以 s“ 开头的字符串可以将 Scala 值 v 引用为 $v 或字符串中的 ${v}。Scala 编译器会将其扩展到 v.toString。

请注意，我们正在捕获异常并将其报告为测试失败，而不是让运行引发错误（这将丢失有关触发失败的参数的信息）。

现在我们有了 Prop 的表示，实现 && 和 ||用于组合道具值。请注意，在失败的情况下，我们不知道哪个属性负责 - 左还是右。您能否设计一种方法来处理此问题，也许通过允许为 Prop 值分配一个在发生故障时显示的标签或标签？

extension (self: Prop) def &&(that: Prop): Prop extension (self: Prop) def ||(that: Prop): Prop

前面我们提到了测试用例最小化的想法，这意味着理想情况下，我们希望我们的框架找到最小或最简单的失败测试用例，以更好地说明问题并促进调试。让我们看看是否可以调整我们的表示来支持这个结果。我们可以采取两种常规方法：

• 收缩 - 找到失败的测试用例后，我们可以运行一个单独的过程，通过连续减小测试用例的大小直到它不再失败来最小化测试用例。这称为收缩，通常需要为每种数据类型编写单独的代码来实现此最小化过程。
• 大小生成 - 我们不是在事后缩小测试用例，而是简单地按大小和复杂性增加的顺序生成测试用例，这意味着我们从小开始，然后增加大小，直到发现失败。这个想法可以通过各种方式扩展，以允许测试运行者在可能的大小空间中进行更大的跳跃，同时仍然可以找到最小的失败测试。

顺便说一下，ScalaCheck采取了第一种方法：收缩。这种方法没有错（Haskell Free Library QuickCheck也使用它，ScalaCheck基于：http://mng.bz/E24n），但我们将看到我们可以用大小生成做什么。它更简单一些，在某些方面也更加模块化，因为我们的生成器只需要知道如何生成给定大小的测试用例。他们不需要知道用于搜索测试用例空间的计划，因此运行测试的函数可以自由选择此计划。我们很快就会看到这种情况如何发展。

与其修改我们的 Gen 数据类型（我们已经为此编写了许多有用的组合器），不如将大小生成作为库中的单独层引入。大小生成器的简单表示只是一个采用大小并生成生成器的函数：

opaque type SGen[ A] = Int => Gen[A]

实现一个帮助程序函数，用于将 Gen 转换为 SGen ，该函数忽略大小参数。您可以将其添加为Gen上的扩展方法：

extension [A](self: Gen[A]) def unsized: SGen[A]

毫不奇怪，SGen 至少支持许多与 Gen 相同的操作，并且实现相当机械。在SGen上定义一些方便的函数，这些函数只是委托给Gen上的相应函数。7

实现不接受显式大小的列表组合器。它应该返回一个 SGen 而不是一个 Gen 。实现应生成请求大小的列表：

extension [A](self: Gen[A]) def list: SGen[List[A]]

让我们看看SGen如何影响Prop和Prop.forAll的定义。SGen 等效的 forAll 如下所示：

@annotation.targetName("forAllSized") ① def forAll[A](g: SGen[A])(f: A => Boolean): Prop

（1） 如果没有此注释，SGen 的 forAll 与 Gen 的 forAll 冲突（假设两者都在 Prop 同伴中定义）。通过此注释，我们消除了编译名称的歧义，避免了冲突。

你能明白为什么无法实现这个功能吗？SGen 希望被告知尺寸，但 Prop 没有收到任何尺寸信息。就像我们对随机性的来源和测试用例的数量所做的那样，我们只需要将其作为依赖项添加到 Prop .但是，由于我们想让 Prop 负责调用具有各种大小的底层生成器，我们将让 Prop 接受最大大小。然后，Prop 将生成最大指定大小（包括指定大小）的测试用例，这也将允许它搜索最小的失败测试用例。让我们看看这是如何解决的。8

清单 8.4 生成最大给定最大大小的测试用例

opaque type MaxSize = Int object MaxSize: extension (x: MaxSize) def toInt: Int = x def fromInt(x: Int): MaxSize = x opaque type Prop = (MaxSize, TestCases, RNG) => Result object Prop: def forAll[A](g: SGen[A])(f: A => Boolean): Prop = (max, n, rng) => val casesPerSize = (n.toInt - 1) / max.toInt 1 ① val props: LazyList[Prop] = LazyList.from(0) .take((n.toInt min max.toInt) 1) ② .map(i => forAll(g(i))(f)) val prop: Prop = props.map[Prop](p => (max, n, rng) => p(max, casesPerSize, rng)) .toList .reduce(_ && _) ③ prop(max, n, rng)

（1）对于每种大小，生成许多随机案例。

（2） 为每个大小创建一个属性，但不超过 n 个属性。

（3）将它们全部合并为一个属性。

我们已经收敛了一个看似合理的API。我们可以继续修补它，但在这一点上，让我们尝试使用库来构建测试，看看我们是否注意到任何缺陷，无论是它可以表达的内容还是它的一般可用性。可用性有些主观，但我们通常喜欢为常见的使用模式提供方便的语法和适当的帮助程序函数。我们不一定是为了让库更具表现力，但我们希望让它使用起来愉快。

让我们重温一下我们在本章开头提到的一个例子：指定函数 max 的行为，可作为 List 上的方法使用（请参阅 API 文档：http://mng.bz/Pz86）。列表的最大值应大于或等于列表中的所有其他元素。让我们指定这一点：

val smallInt = Gen.choose(-10, 10) val maxProp = Prop.forAll(smallInt.list): l => val max = l.max l.forall(_ <= max) ①

（1） ns中不应存在大于最大值的值。

有了这种不透明的类型表示 道具 ，我们需要一种方法来检查我们的属性。让我们定义一个检查扩展方法，该方法评估 Prop 并返回结果。

清单 8.5 Prop 的检查辅助函数

extension (self: Prop) def check( maxSize: MaxSize = 100, ① testCases: TestCases = 100, rng: RNG = RNG.Simple(System.currentTimeMillis) ): Result = self(maxSize, testCases, rng)

（100） 默认参数 <>

为了使在 REPL 中进行实验更容易，我们可以引入一个帮助程序函数来运行我们的 Prop 值并将其结果以有用的格式打印到控制台。

示例 8.6 Prop 的运行辅助函数

extension (self: Prop) def run(maxSize: MaxSize = 100, testCases: TestCases = 100, rng: RNG = RNG.Simple(System.currentTimeMillis)): Unit = self(maxSize, testCases, rng) match case Falsified(msg, n) => println(s"! Falsified after $n passed tests:\n $msg") case Passed => println(s" OK, passed $testCases tests.")

我们在这里利用了默认参数，这使得调用方法更方便。我们希望默认有足够的测试来获得良好的覆盖率，但我们不希望太多测试，以至于它们需要很长时间才能运行。

如果我们尝试运行检查或在 maxProp 上运行，我们注意到该属性失败！基于属性的测试有一种方法可以揭示我们对代码的隐藏假设，并迫使我们对这些假设更加明确。标准库的 max 实现在给定空列表时崩溃。我们需要修复我们的财产以考虑到这一点。

定义用于生成非空列表的非空列表，然后更新 max 的规范以使用此生成器。

让我们再尝试几个例子。

编写一个属性来验证 List.sort 的行为（请参阅 API 文档：http://mng.bz/N4En），您可以使用该属性对 List[Int] 进行排序。9 例如，List（2， 1， 3）.sort 等于 List（1， 2， 3） 。

回想一下，在第7章中，我们发现了应该适用于并行计算的定律。我们可以用我们的图书馆来表达这些规律吗？我们看的第一个定律实际上是一个特定的测试用例：

unit(1).map(_ 1) == unit(2)

我们当然可以表达帕尔的这个定律，但结果有点复杂：10

val executor: ExecutorService = Executors.newCachedThreadPool val p1 = Prop.forAll(Gen.unit(Par.unit(1)))(pi => pi.map(_ 1).run(executor).get == Par.unit(2).run(executor).get)

我们已经表达了测试，但它冗长而混乱，并且测试的想法被此处无关的细节所掩盖。请注意，这不是 API 是否足够表达的问题 - 是的，我们可以表达我们想要的东西，但缺少帮助程序函数和糟糕的语法的组合掩盖了意图。

证明属性

让我们对此进行改进。我们的第一个观察结果是，forAll 对于这个测试用例来说有点太笼统了。我们不会改变此测试的输入;我们只有一个硬编码的例子。硬编码示例应该像在传统的单元测试库中一样方便编写。让我们为它介绍一个组合器（在 Prop 伴侣对象上）：

def verify(p: => Boolean): Prop

我们将如何实现这一点？一种可能的方法是使用 for All：

def verify(p: => Boolean): Prop = ① lazy val result = p ② forAll(unit(()))(_ => result)

（1）我们在这里不严格。

（2）记忆结果以避免重新计算。

这似乎不太对。我们提供了一个仅生成单个值的单位生成器，然后我们继续忽略该值，只是为了驱动给定布尔值的评估。

即使我们记住了结果，因此不会多次评估它，测试运行器仍将生成多个测试用例并多次测试布尔值。例如，如果我们说 verify（true）.run（） ，这将测试属性 100 次并打印 OK，通过了 100 次测试。但是，检查一个始终为真的属性 100 次是一种严重的浪费精力。我们需要的是一个新的原语。

请记住，到目前为止，我们拥有的 Prop 表示只是类型（MaxSize、TestCases、RNG）=> 结果的函数，其中结果要么通过，要么被伪造。验证原语的简单实现是构造一个忽略测试用例数量的 Prop：

def verify(p: => Boolean): Prop = (_, _, _) => if p then Passed else Falsified("()", 0)

这当然比使用 for All 要好，但是 verify（true）.run（） 仍然会打印通过的 100 次测试，即使它只测试一次属性。这样的属性已经通过并不是真的，从某种意义上说，经过多次测试后它仍然没有被伪造。只需一次测试即可证明。似乎我们想要一种新的结果：

enum Result: case Passed case Falsified(failure: FailedCase, successes: SuccessCount) case Proved

然后我们可以在由 verify 创建的属性中返回已证明而不是传递。我们需要修改测试运行程序以考虑这种情况。

清单 8.7 使用 run 处理已证明的对象

extension (self: Prop) def run(maxSize: MaxSize = 100, testCases: TestCases = 100, rng: RNG = RNG.Simple(System.currentTimeMillis)): Unit = self(maxSize, testCases, rng) match case Falsified(msg, n) => println(s"! Falsified after $n passed tests:\n $msg") case Passed => println(s" OK, passed $testCases tests.") case Proved => println(s" OK, proved property.")

我们还需要修改 Prop 组合器的实现，例如 &&。这些变化非常微不足道，因为这样的组合器不需要区分通过和证明的结果。

困难：验证属性很容易最终证明，因为测试只涉及评估布尔参数，但也可以证明一些 forAll 属性。例如，如果属性的域是布尔值，那么实际上只有两种情况需要测试。如果一个属性 forAll（p） 同时通过 p（true） 和 p（false），则它被证明。一些域（例如，布尔值和字节）非常小，可以详尽地检查它们，并且使用大小生成器，甚至可以穷举检查到最大大小。自动化测试非常有用，但如果我们可以自动证明我们的代码正确，那就更好了。修改我们的库以包含对有限域和大小生成器的这种详尽检查。这与其说是一个练习，不如说是一个广泛的、开放式的设计项目。

测试标准杆

回到证明 Par.unit（1）.map（_ 1） 等于 Par.unit（2） 的属性，我们可以使用新的 Prop.verify 原语以一种不掩盖意图的方式表达这一点：

val p2 = Prop.verify: val p = Par.unit(1).map(_ 1) val p2 = Par.unit(2) p.run(executor).get == p2.run(executor).get

这现在已经很清楚了，但是我们可以对 p.run（executor）.get 和 p2.run（executor）.get 噪音做点什么吗？它有一些相当不令人满意的东西。首先，我们强制此代码了解 Par 的内部实现细节，只是为了比较两个 Par 值的相等性。一个改进是使用 map2 将相等比较提升到 Par 中，这意味着我们只需要在最后运行一个 Par 即可获得结果：

def equal[A](p: Par[A], p2: Par[A]): Par[Boolean] = p.map2(p2)(_ == _) val p3 = Prop.verify: equal( Par.unit(1).map(_ 1), Par.unit(2) ).run(executor).get

这比必须单独运行每一侧要好一些。我们甚至可以将 equal 与 forAll 结合使用：

val p4 = Prop.forAll(Gen.smallInt): i => equal( Par.unit(i).map(_ 1), Par.unit(i 1) ).run(executor).get

但是，当我们在这里时，让我们将Par的运行移到一个单独的函数中：forAllPar。这也为我们提供了一个跨不同并行策略插入变体的好地方，而不会弄乱我们指定的属性：

val executors: Gen[ExecutorService] = weighted( ① choose(1, 4).map(Executors.newFixedThreadPool) -> .75, unit(Executors.newCachedThreadPool) -> .25) ② def forAllPar[A](g: Gen[A])(f: A => Par[Boolean]): Prop = forAll(executors.map2(g)((_, _)))((s, a) => f(a).run(s).get)

（75） 此生成器在 25% 的时间内创建一个固定线程池执行器，在 <>% 的时间内创建一个无界的执行器。

（2）a -> b是（a，b）的句法糖。

executors.map2（g）（（_， _）） 是一种相当嘈杂的方式，它结合了两个生成器以产生一对它们的输出。让我们快速引入一个组合器来解决这个问题：11

extension [A](self: Gen[A]) @annotation.targetName("product") ① def **[B](gb: Gen[B]): Gen[(A, B)] = map2(gb)((_, _))

（1） 目标名称注释为符号运算符提供了替代的字母数字名称。通常，始终为每个符号运算符提供字母数字等效项被认为是一种很好的做法。

这要好得多：

def forAllPar[A](g: Gen[A])(f: A => Par[Boolean]): Prop = forAll(executors ** g)((s, a) => f(a)(s).get)

我们甚至可以使用自定义提取器引入 ** 作为模式，这让我们可以编写以下内容：

def forAllPar[A](g: Gen[A])(f: A => Par[Boolean]): Prop = forAll(executors ** g): case s ** a => f(a)(s).get

在更新多个生成器时，此语法效果很好;当模式匹配时，我们不必像直接使用元组模式那样嵌套括号。为了启用 ** 作为模式，我们使用 unapply 函数定义一个名为 ** 的对象：

object `**`: ① def unapply[A, B](p: (A, B)) = Some(p)

（1） ** 周围的反引号是转义，不是对象名称的一部分。

有关此技术的更多详细信息，请参阅自定义提取程序文档 （http://mng.bz/4pUc）。因此，executors 是一个 Gen[ExecutorService]，它将在固定大小的线程池中从 1-4 个线程中变化，并考虑一个无限线程池。现在我们的物业看起来干净多了：12

def verifyPar(p: Par[Boolean]): Prop = ① forAllPar(Gen.unit(()))(_ => p) val p2 = verifyPar: equal( Par.unit(1).map(_ 1), Par.unit(2) )

（1） 验证的变体，它采用 Par[布尔值] 并使用各种执行器来评估属性

这些可能看起来很小的变化，但这种分解和清理可以大大提高我们库的可用性，我们编写的帮助程序函数使属性更易于阅读和编写更愉快。您可能还想为大小生成器添加 forAllPar 版本。

让我们看一下第 7 章中的其他一些属性。回想一下，我们概括了我们的测试用例：

unit(x).map(f) == unit(f(x))

然后，我们将其简化为在计算上映射恒等函数应该没有效果的定律：

y.map(x => x) == y

我们能表达这一点吗？不完全是。此属性隐含地指出，相等适用于 y 的所有选择以及所有类型的选择。我们被迫为 y 选择特定的值：

val gpy: Gen[Par[Int]] = Gen.choose(0,10).map(Par.unit(_)) val p5 = Prop.forAllPar(gpy)(py => equal(py.map(y => y), py))

我们当然可以提供更多的y选择，但我们在这里拥有的可能已经足够好了。map 的实现不能关心我们并行计算的值，所以为 Double 、String 等构造相同的测试没有多大意义。并行计算的结构可能会影响地图。如果我们想更好地保证我们的财产持有，我们可以为结构提供更丰富的发电机。在这里，我们只为具有一个嵌套级别的 Par 表达式提供。

困难：为 Par[Int] 编写一个更丰富的生成器，它构建比我们之前给出的简单计算更深入嵌套的并行计算。

表达第 7 章中关于 fork 的属性——fork（x） == x 。

到目前为止，我们的库似乎很有表现力，但有一个方面是缺乏的：我们目前没有测试高阶函数的好方法。虽然我们有很多使用生成器生成数据的方法，但我们并没有真正生成函数的好方法。

例如，让我们考虑为 List 和 LazyList 定义的 takeWhile 函数。回想一下，此函数返回其输入的最长前缀，其元素都满足谓词 - 例如，List（1， 2， 3）.takeWhile（_ < 3） 结果为 List（1， 2） 。我们要检查的一个简单的属性是，对于任何列表，如：List[A]，以及任何f：A =>布尔值，表达式as.takeWhile（f）.forall（f）的计算结果为true。也就是说，返回列表中的每个元素都满足谓词。13

想出一些其他属性，需要同时满足。你能想到一个表达 takeWhile 和 dropWhile 之间关系的好属性吗？

困难：我们想要生成一个函数，该函数以某种方式使用其参数来选择要返回的 Int。你能想到一个好的方式来表达这一点吗？这是一个非常开放且具有挑战性的设计练习。看看你能发现的关于这个问题有什么，以及是否有一个很好的通用解决方案，你可以合并到我们迄今为止开发的库中。

尝试冒险并使用我们开发的库！看看你还能用它测试什么，看看你是否发现了任何新的习语，或者也许可以进一步扩展或更方便的方法。以下是一些帮助您入门的想法：

• 编写属性来指定我们为 List 和 LazyList 编写的其他一些函数的行为，例如，take 、drop 、filter 和 unfold 。
• 编写一个大小生成器来生成第 3 章中定义的 Tree 数据类型，然后使用它来指定我们为 Tree 定义的折叠函数的行为。你能想到任何改进 API 的方法来简化这一点吗？
• 编写属性，指定我们为 Option 和 要么 定义的序列函数的行为。

我们为Gen类型实现的许多函数看起来与我们在Par，List，LazyList和Option上定义的其他函数非常相似，这不是很有趣吗？例如，对于 Par，我们定义了以下内容：

extension [A](pa: Par[A]) def map[B](f: A => B): Par[B]

在本章中，我们为Gen定义了map：

extension [A](ga: Gen[A]) def map[B](f: A => B): Gen[B]

我们还为 Option 、List 、LazyList 和 State 定义了外观相似的函数。我们不得不怀疑我们的函数是否只是共享相似的签名，或者它们也满足相同的定律。让我们看一下我们在第7章中为Par引入的法律：

y.map(id) == y

这条法律是否适用于我们实施Gen.map？对于 LazyList、List 、Option 和 State 呢？是的，确实如此！试试看。这表明这些函数不仅共享外观相似的签名，而且在某种意义上，它们在各自的域中也具有相似的含义。看来有更深层次的力量在起作用！我们正在揭示一些跨越领域的基本模式。在第 3 部分中，我们将学习这些模式的名称，发现管理它们的规律，并了解这一切的含义。

在本章中，我们完成了函数库设计的另一个扩展练习，使用基于属性的测试领域作为灵感。我们重申，我们的目标不一定是学习基于属性的测试，而是强调功能设计的特定方面。

首先，我们看到在抽象代数和具体表示之间振荡可以让两者相互通知。这避免了将库过度拟合到特定的表示形式，并防止我们最终得到与最终目标断开连接的浮动抽象。其次，我们注意到这个域使我们发现了许多我们以前见过几次的相同组合器：map，flatMap等。不仅这些函数的签名是相似的，而且实现满足的定律也是类似的。在软件世界中，有许多看似不同的问题正在解决，但功能解决方案的空间要小得多。许多库只是某些基本结构的简单组合，这些结构在各种不同的领域中反复出现。这为代码重用提供了一个机会，我们将在第 3 部分中学习其中一些结构的名称以及如何发现更通用的抽象时利用这些机会。

在第 2 部分的下一章也是最后一章中，我们将介绍另一个领域，解析，它有其独特的挑战。我们将在这一章中采用略有不同的方法，但再次出现熟悉的模式。

• 我们的 API 的属性可以自动测试，在某些情况下，还可以使用基于属性的测试进行验证。
• 属性可以表示为一个函数，该函数采用任意输入值并基于这些输入断言所需的结果。
• 在本章开发的库中，Prop 类型用于对这些属性进行建模。
• 以这种方式定义的属性断言有关所测试功能的各种不变量 - 对于所有可能的输入值都应该为真。此类属性的一个示例是，反转列表然后对元素求和应与对原始列表求和相同。
• 为任意输入值定义属性需要一种生成此类值的方法。
• 在本章开发的库中，Gen 和 SGen 类型用于任意值生成。
• 测试用例最小化是基于属性的测试库查找属性失败的最小输入值的能力。
• 详尽的测试用例生成是生成属性的所有可能输入的能力。这仅适用于有限域，并且仅在域大小较小时才实际可能。
• 如果对属性的每个可能输入都经过测试并且全部通过，则证明该属性为真。相反，如果该属性对于任何生成的输入都没有失败，则传递该属性。可能仍有一些输入未生成，但属性失败。
• 像map和flatMap这样的组合器继续出现在我们创建的数据类型中，它们的实现满足相同的定律。

• 空列表的总和为 0— sum（Nil） == 0 。
• 元素都等于 x 的列表的总和是列表的大小乘以 x — sum（List.fill（n）（x）） == n * x 。
• 对于任何列表 xs，其总和等于 xs.reverse 的总和;也就是说，sum（xs） == sum（xs.reverse） 。这是因为加法是可交换的。
• 对于任何列表 xs，将其分区为两个列表，对每个分区求和，然后将总和相加会产生与求和 xs 相同的结果。这是因为加法是结合的。
• 包含元素 1、2、3 的列表的总和...n 是 n*（n 1）/2 。

• 空列表的最大值为错误。
• 单个元素列表的最大值就是该元素。
• 元素都等于 x 的列表的最大值是 x 。
• 列表的最大值是列表中的一个元素。
• 列表的最大值大于或等于列表中的每个元素。

现在 check 返回了一个布尔值，我们可以实现 &&对第一个属性调用 check，如果通过，则对参数调用 check：

trait Prop: self => ① def check: Boolean def &&(that: Prop): Prop = new Prop: def check = self.check && that.check

（1） 此语法为此引入了一个别名，稍后我们需要引用外部 Prop 实例。

我们可以通过首先生成一个随机的非负整数，然后将该整数移动到请求的范围来实现选择。由于 Gen[A] 是状态 [RNG， A] 的不透明类型，我们必须返回一个状态操作，其中 RNG 是状态类型。

回想一下我们在第6章中写的非NegativeInt函数，它的签名为def nonNegativeInt（rng：RNG）：（Int，RNG）。我们可以将该函数与 State 包装在一起，以获得生成非负整数的状态操作。然后我们可以使用将整数移动到正确范围的函数来映射它：

def choose(start: Int, stopExclusive: Int): Gen[Int] = State(RNG.nonNegativeInt).map(n => start n % (stopExclusive - start))

unit 的实现可以直接重用 state.unit，给定 Gen[A] 等价于 State[RNG， A]：

def unit[A](a: => A): Gen[A] = State.unit(a)

同样，布尔可以重用 RNG.boolean 的定义，它具有签名 def boolean（rng： RNG）：（Boolean， RNG）。与 nonNegativeInt 一样，我们只需要将其包装到状态操作中：

def boolean: Gen[Boolean] = State(RNG.boolean)

最棘手的是 列表OfN .我们首先创建一个包含 n 个元素的列表，其中每个元素都是提供的生成器。这样做会给我们一个列表[Gen[A]]，但是由于Gen[A] = State[RNG，A]，这实际上是一个列表[状态[RNG，A]]。有了这些知识，我们就可以使用State.sequence来翻转Gen和List的位置，给我们所需的Gen[List[A]]：

extension [A](self: Gen[A]) def listOfN(n: Int): Gen[List[A]] = State.sequence(List.fill(n)(self))

我们可以直接在 State 上重用 flatMap 操作 — 有一个陷阱。我们正在定义的平面映射扩展方法优先于状态上的平面映射扩展方法。因此，自然表达式 ga.flatMap（f） 不会在 State 上调用 flatMap，而是导致无限递归。我们可以通过直接调用扩展方法来指示我们确实想要在 State 上定义的方法：

extension [A](self: Gen[A]) def flatMap[B](f: A => Gen[B]): Gen[B] = State.flatMap(self)(f)

使用 flatMap ，然后我们可以实现 listOfN 的变体，根据我们之前定义的 listOfN 方法，它将大小作为 Gen[Int]，该方法采用整数大小参数：

extension [A](self: Gen[A]) def listOfN(size: Gen[Int]): Gen[List[A]] = size.flatMap(listOfN)

由于我们想要相等的可能性，我们可以使用我们之前定义为抛硬币的布尔生成器，在获得 true 时选择 g1，在获得 false 时选择 g2。我们在布尔值上使用 flatMap，以便在选择后续生成器时能够访问抛硬币结果：

def union[A](g1: Gen[A], g2: Gen[A]): Gen[A] = boolean.flatMap(b => if b then g1 else g2)

加权可以用类似于并集的方式实现，除了不是抛硬币，我们计算概率 [0， 1）。然后，当生成的概率小于归一化权重时，我们选择 g1：

def weighted[A](g1: (Gen[A], Double), g2: (Gen[A], Double)): Gen[A] val g1Threshold = g1(1).abs / (g1(1).abs g2(1).abs) State(RNG.double).flatMap(d => if d < g1Threshold then g1(0) else g2(0))

要实现 &&，我们可以返回一个函数，该函数首先在 && 的左侧运行属性，如果成功，则在右侧运行该属性：

extension (self: Prop) def &&(that: Prop): Prop = (n, rng) => self(n, rng) match case Passed => that(n, rng) case x => x

我们可以实施 ||以类似的方式，先运行 left 属性，然后仅在 left 失败时运行 right 属性：

extension (self: Prop) def ||(that: Prop): Prop = (n, rng) => self(n, rng) match case Falsified(_, _) => that(n, rng) case x => x

我们还定义一种运行属性的方法，以便我们可以在 REPL 中试验它们（我们将在本章后面扩展检查和运行属性的概念;现在，我们只需要一种调用底层函数并打印结果的方法）：

extension (self: Prop) def run(): Unit = self(100, RNG.Simple(System.currentTimeMillis)) match case Falsified(msg, n) => println(s"! Falsified after $n passed tests:\n $msg") case Passed => println(s" OK, passed $testCases tests.")

run（） 方法使用具有 100 个测试用例和用当前时间初始化的 RNG 计算属性。然后，它将结果打印到控制台。

&& 和 || 的实现工作，但在发生故障时未提供足够的信息。请考虑以下示例，其中 p 是始终传递的属性，q 是随机失败的属性：

val p: Prop = Prop.forAll(Gen.boolean)(x => x == x) val q: Prop = Prop.forAll(Gen.boolean)(x => x)

运行使用 && 和 || 构建的复合属性时，我们没有获得有关哪个构成属性导致失败的任何信息：

scala> (p && q).run() ! Falsified after 4 passed tests: false scala> (q && p).run() ! Falsified after 1 passed tests: false scala> (q || q).run() ! Falsified after 2 passed tests: false

我们可以通过向 Prop 添加一个标签组合器来解决这个问题，它装饰在 Falsified 情况下返回的错误消息：

extension (self: Prop) def tag(msg: String): Prop = (n, rng) => self(n, rng) match case Falsified(e, c) => Falsified(FailedCase.fromString(s"$msg($e)"), c) case x => x

此实现将原始错误消息与传递给 tag 的消息包装在一起，尽管更复杂的实现可以更改 Falsified 类型以存储更丰富的数据结构，如表达式堆栈或树。我们还需要记住在 && 和 || 的实现中使用 tag。:

extension (self: Prop) def &&(that: Prop): Prop = (n, rng) => self.tag("and-left")(n, rng) match case Passed => that.tag("and-right")(n, rng) case x => x extension (self: Prop) def ||(that: Prop): Prop = (n, rng) => self.tag("or-left")(n, rng) match case Falsified(msg, _) => that.tag("or-right").tag(msg.string)(n, rng) case x => x

我们的错误消息现在提供了有关属性的哪些部分失败的提示：

scala> (p && q).run() ! Falsified after 4 passed tests: and-right(false) scala> (q && p).run() ! Falsified after 1 passed tests: and-left(false) scala> (q || q).run() ! Falsified after 2 passed tests: or-left(false)(or-right(false))

由于 SGen 只是一个从大小到世代的函数，我们可以返回一个忽略大小参数的匿名函数：

extension [A](self: Gen[A]) def unsized: SGen[A] = _ => self

我们先实现地图：

extension [A](self: SGen[A]) def map[B](f: A => B): SGen[B] = n => self(n).map(f)

实现可以仅通过以下类型来确定。我们需要返回一个 SGen[B]，所以我们构建了一个从大小 （n） 到 Gen[B] 的匿名函数。为了获得一个Gen[B]，我们将size参数应用于原始SGen[A]，给我们一个Gen[A]。最后，我们在 Gen 上使用我们的映射函数将该 Gen[A] 转换为 Gen[B]。这种类型引导的实现就是我们所说的机械。

让我们再做一个 - 平面地图：

extension [A](self: SGen[A]) def flatMap[B](f: A => SGen[B]): SGen[B] = n => self(n).flatMap(a => f(a)(n))

使用相同的技术，我们返回一个匿名函数，该函数采用大小并返回 Gen[B] 。我们将大小应用于原始SGen[A]，给我们一个Gen[A]。我们在那个Gen[A]上调用flatMap，但我们不能像map那样将f传递给flatMap;flatMap 想要一个函数 A => Gen[B]。因此，我们传递一个函数，该函数首先将 a 应用于 f ，返回一个 SGen[B]，然后将大小参数应用于该 SGen[B] 以将其转换为 Gen[B]。

我们可以返回一个匿名函数，该函数将大小作为参数并将其应用于我们之前编写的 listOfN 方法：

extension [A](self: Gen[A]) def list: SGen[List[A]] = n => self.listOfN(n)

我们可以使用与 listOf 相同的实现，但需要检查以确保传递给 listOfN 的大小至少为 1 ：

extension [A](self: Gen[A]) def nonEmptyList: SGen[List[A]] = n => listOfN(n.max(1)) val maxProp = Prop.forAll(smallInt.nonEmptyList): ns => val max = ns.max !ns.exists(_ > max) scala> maxProp.run() OK, passed 100 tests.

对任意列表进行排序的输出应该是每个元素小于或等于下一个元素的列表。我们可以将其写为属性，方法是用尾部压缩列表的元素，然后验证每对都遵守此排序要求。我们还需要验证排序列表是否包含原始列表中的所有元素，而没有其他元素：

val sortedProp = Prop.forAll(smallInt.list): l => val ls = l.sorted val ordered = l.isEmpty || ls.zip(ls.tail).forall((a, b) => a <= b) ordered && l.forall(ls.contains) && ls.forall(l.contains)

我们可以增强Gen[A]的能力，使其能够详尽地列出域的成员，同时保留选择随机样本和描述无限域的能力。一种这样的编码是将随机生成器与详尽的元素列表配对：

case class Gen[ A](sample: State[RNG, A], exhaustive: LazyList[Option[A]])

在这里，我们选择将有限、详尽的域元素列表建模为惰性选项列表。该列表提供包装在 Some 中的域的每个值，直到我们枚举了每个元素，然后返回一个空列表。对于无限域，我们将穷举设置为单个 None 的列表，表明该域没有穷举枚举。

我们可以为这个新版本的Gen实现map2吗？是的！一起来看看：

case class Gen[ A](sample: State[RNG, A], exhaustive: LazyList[Option[A]]): def map2[B, C](g: Gen[B])(f: (A, B) => C): Gen[C] = Gen(sample.map2(g.sample)(f), map2LazyList(exhaustive, g.exhaustive)(map2Option(_,_)(f)))

在这里，我们使用 LazyList 和 Option 上的 map2 来组合穷举值。14 这太强大了！我们可以生成两个或多个穷举生成器的笛卡尔积。

接下来，我们需要修改 for All 以使用此新的 Gen 类型。请记住，Prop 是从 （MaxSize， TestCases， RNG） 到 Result 的函数。特别令人感兴趣的是 TestCases 参数，它可能小于域中的元素数。在运行属性时，我们应该尊重指定数量的测试用例。如果域的大小小于指定数量的测试用例，我们可以明确地证明我们的属性。否则，鉴于我们运行的测试用例，我们只能声称我们没有找到失败的测试用例。因此，我们将稍微改变对属性测试结果进行建模的方式，以提供这种表现力：

enum Status: case Proven, Unfalsified enum Result: case Falsified(failure: FailedCase) case Passed(status: Status, testCases: TestCases)

属性结果现在表示为已被伪造或在一定数量的测试用例后通过，以及显示属性是否已被证明或根本没有伪造的指示器。

回到 forAll ，我们需要决定测试用例的策略。一个选项是首先运行穷尽列表中的所有示例，直到指定数量的测试用例。如果我们到达该列表的末尾，在评估样本时没有遇到 None 或失败，那么我们已经证明了该属性，因为我们已经针对域的每个元素进行了测试。相反，如果我们遇到一个 无 ，我们可以使用 sample 随机生成必要的附加测试用例。

但是，这种方法存在问题。如果 TestCases 参数小于域的大小，则每次运行该属性时，我们都会运行相同的测试用例。我们可以通过在切换到随机样本之前限制我们使用的详尽列表中的元素数量来解决这个问题。在下面的 forAll 实现中，我们决定从详尽列表中获取三分之一的测试用例，其余的作为随机样本：

def forAll[A](a: Gen[A])(f: A => Boolean): Prop = (max, n, rng) => def go(i: Int, j: Int, l: LazyList[Option[A]], onEnd: Int => Result ): Result = if i == j then Passed(Unfalsified, i) else l match case Some(h) #:: t => try if f(h) then go(i 1, j, t, onEnd) else Falsified(h.toString) catch case e: Exception => Falsified(buildMsg(h, e)) case None #:: _ => Passed(Unfalsified, i) case _ => onEnd(i) val numFromExhaustiveList = TestCases.fromInt(n.toInt / 3) go(0, numFromExhaustiveList, a.exhaustive, i => Passed(Proven, i)) match case Passed(Unfalsified, _) => val rands = randomLazyList(a)(rng).map(Some(_)) go(numFromExhaustiveList, n, rands, i => Passed(Unfalsified, i)) case s => s // If proven or failed, stop immediately

下面是一个用法示例：

scala> val andCommutative = Prop.forAll(Gen.boolean.map2(Gen.boolean)((_, _))): (p, q) => (p && q) == (q && p)) scala> andCommutative.run() OK, property proven, ran 4 tests.

随附的 GitHub 存储库中的源代码扩展了此解决方案，以涵盖大小的生成器。

一种技术是生成一个 List[Int]，然后将该列表折叠成单个 Par[Int]，其中每个组合都分叉计算：

val gpy2: Gen[Par[Int]] = choose(-100, 100).listOfN(choose(0, 20)).map(ys => ys.foldLeft(Par.unit(0))((p, y) => Par.fork(p.map2(Par.unit(y))(_ _))))

我们通过 choose（-100， 100）.listOfN（choose（0， 20）） 创建一个 Gen[List[Int]]。然后，我们映射该生成器，并使用 fork 和 map2 将列表减少到单个 Par[Unit]。我们可以在列表上提取一个新的泛型函数 parTraverse ，并使用它来实现我们的生成器：

extension [A](self: List[A]) def parTraverse[B](f: A => Par[B]): Par[List[B]] = self.foldRight(Par.unit(Nil: List[B]))((a, pacc) => Par.fork(f(a).map2(pacc)(_ :: _))) val gpy3: Gen[Par[Int]] = choose(-100, 100).listOfN(choose(0, 20)).map(ys => ys.parTraverse(Par.unit).map(_.sum))

我们可以直接通过 forAllPar 和我们之前编写的 Gen[Par[Int]] 来表达这一点：

val forkProp = Prop.forAllPar(gpy2)(y => equal(Par.fork(y), y))

要求 as.takeWhile（f）.forall（f） == true 不会强制 takeWhile 返回属性所包含的最长可能前缀。为了验证这一点，我们可以引入另一个属性，该属性表示剩余列表的头部（如果不是空的）必须使谓词失败 - 类似于 ！f（as（as.takeWhile（f）.size）），但处理 as.size == as.takeWhile（f）.size 的情况。另一个属性描述了 takeWhile 和 dropWhile 的关系：将调用 takeWhile 的结果与在同一列表中调用 dropWhile 的结果连接起来应该产生相同的列表。

如果我们尝试使用我们的库编写这些属性中的任何一个，我们会遇到问题。这些属性中的每一个都需要一个 Gen[Int => 布尔值]，但我们没有生成函数的方法。

我们当然可以采取在测试高阶函数时只检查特定参数的方法。例如，这里有一个更具体的 takeWhile 属性：

def isEven(i: Int) = i % 2 == 0 val takeWhileProp = Prop.forAll(Gen.int.list)(ys => ys.takeWhile(isEven).forall(isEven))

这有效，但是有没有办法让测试框架处理生成函数以与takeWhile 一起使用？15 让我们考虑一下我们的选择。为了具体化，假设我们有一个Gen[Int]，并希望生成一个Gen[String => Int]。我们有什么方法可以做到这一点？一种选择是生成 String => Int 函数，这些函数只需忽略其输入字符串并委托给底层 Gen[Int]：

def genStringIntFn(g: Gen[Int]): Gen[String => Int] = g.map(i => (s => i))

但是，这种方法还不够;我们只是生成忽略其输入的常量函数。在takeWhile的情况下，我们需要一个返回布尔值的函数，这将是一个总是返回true或总是返回false的函数——这对于测试我们函数的行为显然不是很有趣。

让我们首先看一下激励示例的签名，从 String => Int 生成一个函数，给定一个 Gen[Int]：

def genStringIntFn(g: Gen[Int]): Gen[String => Int]

现在让我们对此进行一些概括，以便它不是专门用于 Int 的，因为这会让我们作弊（例如，返回输入字符串的哈希代码，恰好是一个 Int ）：

def genStringFn[A](g: Gen[A]): Gen[String => A]

我们已经排除了只返回一个忽略输入字符串的函数，因为这不是很有趣！相反，我们希望确保使用来自输入字符串的信息来影响我们生成的 A。我们该怎么做呢？我们可以对Gen产生的值产生影响的唯一方法是修改它作为输入接收的RNG值。

回想一下我们对Gen的定义：

opaque type Gen[ A] = State[RNG, A]

只需遵循类型，我们就可以开始编写以下内容：

def genStringFn[A](g: Gen[A]): Gen[String => A] = State[RNG, String => A]: rng => ???

???必须是类型（字符串 => A，RNG），此外，我们希望字符串以某种方式影响生成的 A。我们通过修改 RNG 的种子，然后再将其传递给 Gen[A] 示例函数来实现这一点。一种简单的方法是计算输入字符串的哈希并将其混合到 RNG 状态中，然后再使用它来生成 A：

def genStringFn[A](g: Gen[A]): Gen[String => A] = State[RNG, String => A]: rng => val (seed, rng2) = rng.nextInt ① val f = (s: String) => g.run(RNG.Simple(seed.toLong ^ s.hashCode.toLong))(0) (f, rng2)

（1）我们仍然使用rng来产生种子，所以我们每次都会得到一个新的函数。

更一般地说，可以使用任何接受字符串和 RNG 并生成新 RNG 的函数。在这里，我们计算字符串的哈希代码，然后使用带有种子值的独占或（XOR）来生成新的RNG。我们可以很容易地获取字符串的长度，并使用此值来扰乱我们的 RNG 状态或获取字符串的前三个字符。这些选择会影响我们正在生产的功能类型：

• 如果我们使用 hashCode 来扰乱 RNG 状态，我们生成的函数将使用 String 的所有信息来影响生成的 A 值。只有共享相同哈希码的输入字符串才能保证产生相同的 A。
• 如果我们使用 长度 ，我们正在生成的函数只是使用字符串的某些信息来影响正在生成的 A。对于所有具有相同长度的输入字符串，我们保证得到相同的 A 。

我们选择的策略取决于我们认为哪些函数对于我们的测试是现实的。我们想要使用所有可用信息来生成结果的函数，还是对仅使用其输入的零碎的函数更感兴趣？我们可以将策略包装为一种类型：

opaque type Cogen[-A] = (A, RNG) => RNG

有了这个新类型，我们可以泛化 genStringFn 以适用于任何输入类型：

def fn[A, B](in: Cogen[A], out: Gen[B]): Gen[A => B] = State[RNG, A => B]: rng => val (seed, rng2) = rng.nextInt val f = (a: A) => out.run(in(a, rng2))(0) (f, rng2)

此方法的一个问题是向用户报告测试用例失败。如果发生故障，用户将看到的只是对于某些不透明的函数，属性失败了，这不是很有启发性。Haskell免费库QuickCheck（http://mng.bz/MvYW）中已经有工作能够向用户报告，甚至将生成的函数缩小到最简单的形式，仍然会伪造属性。有关更多信息，请参阅Malcolm Wallace在2012年Haskell研讨会上关于缩小和显示功能的演讲：http://mng.bz/aZq7。

随附的 GitHub 存储库中的源代码使用本章中开发的库对本书中出现的练习进行单元测试。看看如何测试各种属性。

1 这种测试的目标不一定是完全指定程序行为，而是为代码提供更大的信心。就像一般的测试一样，我们总是可以使我们的属性更完整，但我们应该进行通常的成本效益分析，以确定额外的工作是否值得做。

2 域的用法与函数的域相同（http://mng.bz/ZP8q）;生成器描述了我们想要测试的函数的可能输入。请注意，我们有时仍然会使用更通俗意义上的域来指代感兴趣的主题或领域，例如，功能并行域或错误处理域。

3 这可能会让你想起我们在第7章中讨论的类似问题，当时我们研究了使用Thread和Runnable进行并行。

4 从某种意义上说，我们可以将 Prop 建模为 （） => 布尔值，而不是使用单一方法的特征，而不会失去任何表现力。

5 回想一下以下定义：不透明类型 State[S， A] = S => （A， S） 。

6 从某种意义上说，我们可以用返回 要么 的 thunk 替换特征。

7 在第 3 部分中，我们将讨论排除这种重复的方法。

8 这个相当简单的实现为生成的每个大小提供了相同数量的测试用例，并将大小增加 1，从 0 开始。我们可以想象一个更复杂的实现，它更像是对失败的测试用例大小进行二进制搜索 — 从大小 0，1，2，4，8，16 开始......然后在发生故障时缩小搜索空间。

9 sorting对列表的元素采用隐式排序来控制排序策略。

10 这是使用我们对Par[A]的初始编码，它在运行时返回java.util.concurrent.Future[A]。

11 调用这个 ** 实际上是合适的，因为这个函数取两个生成器的乘积，正如我们在第 3 章中讨论的意义上。

12 我们不能在 Scala 中使用标准的 Java/Scala equals 方法或 == 方法（委托给 equals 方法），因为该方法直接返回布尔值，我们需要返回 Par[布尔值]。

13 在 Scala 标准库中，forall 是 List 和 LazyList 上的一个方法，签名为 def forall [A]（f： A => Boolean）：布尔值。

14 此处省略了 map2LazyList 和 map2Option 的定义（参见本章随附的答案源代码中的 Exhaustive.scala）。

15 回想一下，在第7章中，我们介绍了自由定理的概念，并讨论了参数化如何使我们不必检查每种类型的参数的函数行为。尽管如此，在许多情况下，能够生成用于测试的函数是有用的。