我们在上一篇文章：Scala 纯函数式库设计：并行编程 - 掘金 (juejin.cn) 引入了代数式设计 API 的观点。它表现为一些数据类型以及基于这些类型的函数。更重要的是那些表达了函数彼此间关联的定律和性质。
本文的性质，通俗来说，可以指代在一定的约束下，某个 API 所表现出的，可被描述出规律的行为。比如，假定一个列表元素求和的函数 List[Int] => Int，可以想象出它应该有以下的性质：
翻转列表求和与原始列表求和的结果一致。
如果列表的所有值全部一样，则求和结果一定满足 size * n。
若列表内的元素值全部是非负的，那返回值也一定是非负的。
在这之前，我们似乎很少从性质的角度出发编写测试。比如说，验证如下的除法函数是否能返回期望的结果：
def div(a : Int, b : Int) = a / b
我们可能只会考虑在 JUnit 中编写一个简单的特例，如： div(6,2) 来验证它是否正常工作。事实上，这种测试会遗漏一些边界条件：比如传入的数如果为 0，负数，或是一个很大的数值时，这个 div 函数是否还能表现出正常的行为？当 a 无法被 b 整除时，它又会返回什么样的结果？
手工编写大量的单元测试验证这些性质是费时费力的事情，但此处已经隐晦地表示了以自动化的方式验证这些性质是可能的。本章的专题就是探讨如何创建一个简单且强大的基于性质的测试库 ( property-based testing )。开发人员只需要阐述程序的行为，抽象测试用例的约束。框架会使用 生成器 自动生成满足约束的测试用例，并以此验证程序在约束下的行为 ( 或称 "性质" ) 是否满足预期。
然而，这类测试通常不会覆盖所有可能的行为，而是进一步保证程序不会发生意外的错误。我们当然可以考虑用更完整的测试来验证性质是否成立，但也要考虑到时间代价。
基于性质的测试库还有一些其它的特性。
测试用例最小化 —— 一旦测试失败，框架就会尝试去缩小范围，直到明确导致失败的最小集合。比如当列表的长度为 0 时，某个 API 的性质就会失效。框架会尝试着缩小列表的长度，直到发现这个最小的情况并告诉我们。
穷尽测试用例 —— 在某些情况下，问题的定义域 ( domain ) 足够小时，我们干脆穷尽所有的值来进行测试，而不是其中一部分样例数据。当性质可以囊括所有空间的值时，我们可以在无任何疏忽的情况下论证这条性质。
Scala 已经有了基于性质的测试框架 ScalaCheck。ScalaCheck 的设计受 Haskell 的 QuickCheck 的启发，同时也设计了独有的特性。ScalaCheck 已经被用于主流的 Scala 项目，如 Scala 编译器和 Akka 并发编程框架。
在这里，我们会自行尝试设计一个这样的库，目的仍然是为了把玩函数式编程，尽管这可能意味着一个曲折复杂的过程。在最开始，我们或许可以先从 ScalaCheck 那里获取一些灵感。比如：
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)
目前暂时不清楚 Gen.choose 和 Gen.listOf 都是如何实现的，但是应该能推测出来它们返回一个参数化的类型。比如，Gen.choose(0,100) 极有可能返回一个 Gen[Int]，而 Gen.listOf 返回一个 Gen[List[Int]]。基于这种假设，不妨将 Gen.listOf 定义为：
def listOf[A](a : Gen[A]) : Gen[List[A]]
不过，当前的 listOf 方法似乎没有指明生成列表的长度。为了方便实现，我们可能会假设有这样的 API：
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]
上面的示例中还剩下一个 forAll 函数。它接收一个 Gen[List[A]] 和 List[A] => Boolean 的 谓词 ( predicate )。另一方面，我们假定测试的结果返回一个 prop 类型，它是 property 属性 / 性质的简写。尽管目前不知道它还有哪些方法，但我们期望多个性质 Prop 至少是可以使用 && 组合的，以表示某一个测试同时满足多条性质。
def forAll[A](a : Gen[A])(f : A => Boolean) : Proptrait Prop{def &&(p : Prop) : Prop}性质 Prop 的含义与 API
现在已经具备一些基本的 API 了，剩下要做的就是讨论这些 API 的意义。对于 Prop ，现在已经存在的 API 有：
forAll：创建某个性质。
&&：将多个性质进行组合。
还需要一个 check 方法运行性质。
check 方法应当返回一个有意义的值，否则就没有办法进行组合。比如，我们无法使用这样的 check 方法实现 &&：
trait Prop : def check : Unit def &&(p : Prop) : Prop = ???
在测试之后，至少得知道一个性质是成立还是失效的。因此令 check 方法返回一个 Boolean 类型，然后基于此实现 && 方法。
trait Prop : // 通过 self 指代这个 Prop 自身。 self => def check : Boolean def &&(p : Prop) : Prop = new Prop : // 如果使用 this.check，则会错误地声明一个递归方法。 override def check: Boolean = self.check && p.check
目前的实现存在一些缺陷：尽管现在可以使用 && 组合任意多个的 Prop，但是我们希望当测试失败时，程序会反馈哪些之前的测试是成功的，而什么样的参数又导致了失败。因此，假定返回一个 Either 类型来表示这个 Prop 是成功 / 失败了。
object Prop : // 在伴生对象中创建类型别名 type SuccessCount = Inttrait Prop : def check : Either[???,SuccessCount]
当测试成功的时候，仅返回一个 Int 类型表示测试成功的数量就好。那么测试失败的时候应当返回什么呢？凭借以往编写单元测试的经验来看，当测试不通过时，像 Scalatest 这样的测试框架仅仅是简单地将失败的那个测试输出到控制台上，以便开发者去修复它。
这样来看，使用 String 字符串来记录失败的那个测试样例最好。现在，Prop 的内容被拓展成了：
trait Prop : import Prop._ def check : Either[(FailedCase,SuccessCount),SuccessCount] def &&(p : Prop) : Prop = ???object Prop: type SuccessCount = Int type FailedCase = String
由于 check 方法现在返回的不再是简单的 Boolean 类型，因此不妨等到后面再实现 && 方法。显然，在失败的情形下，返回的将是 Left(s,n)：s 描述了失败的测试信息，n 描述了在此之前测试成功的数目。
这里刻意地为 Int 和 String 赋予更有意义的类型别称 ( 后文还有其它的 )，是因为在匿名表达式的代码提示中，所有的参数都被 v1，v2 这样的命名代替。此举也是为了给调用代码的用户以明确的线索和提示。
Prop 类型还有一个待实现的 forAll 方法：
def forAll[A](a : Gen[A])(f : A => Boolean) : Prop
到目前为止，我们无法从任何渠道获取函数 f 所需要的 A 类型参数，但知道它应该是生成器 a 通过某种方式来传递的。为了更好地梳理 Prop 和 Gen 之间的关系，现在将注意力转移到 Gen 的实现上。
生成器 Gen 的实现
我们在前文定义了 Gen[A] 是用于生成 A 类型的值的生成器。至于具体的生成方式可以设定为随机的。回想在早些时候，我们曾实现了一个函数式生成器 RandomGen[A]，以及抽象的状态转移类型。这里首先给出部分声明：
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)0
如果要回顾 State 和生成器本身的设计，需要查看 Scala：在纯函数中优雅地转移状态 - 掘金 (juejin.cn)。我们的 Gen[A] 将是一个包装了随机数生成器的状态机：
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)1
基于此，Gen.choose 函数可以实现为：
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)2
尝试实现更多的功能，比如 unit，boolean 和 listOfN：
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)3
基本的函数如 Gen.listOfN 和 Gen.choose 已经实现的差不多了，现在用一个简单的例子去验证设计。比如：尝试利用已有的 API 生成一个长度为 5，元素值域在 [0,1000) 之间的数组序列：
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)4
提取基础组合子
随着 API 的拓展，我们自然而然就会思考一个问题：哪些操作是 衍生 的，哪些操作是 原生 的。在函数式编程中，我们总是尽可能使用最少但最富有表现力的一组原生操作去构建出丰富的衍生操作集合。
假设现在要创建一个 Gen[(String,String)] 类型的生成器。在这生成的一对字符串中，第二个字符串依赖于第一个字符串生成。这种情况下，我们可以引出 flatMap 组合子：它允许一个生成器依赖另一个生成器。
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)5
这里从类型推导的角度给出 flatMap 的实现思路：
Gen[B] 内部需要一个 State[S,B] 的状态转移类型，现在已知函数 f 能够返回一个 gb : Gen[B]。通过调用 gb.state 可以获得 State[S,B]，但是 f 需要接收一个 A 类型的参数 a。而当前生成器 ( this ) 的状态是 State[S,A]，通过调用 this.state.flatMap 组合子则正好能提供一个 A 参数。
同时，这里的 listOfN 方法是 flatMap 组合子的其中一个实践。它是一个动态生成器：随机生成不定长度的序列，而这个长度又是由另一个生成器指定的。该方法底层调用了 Gen.listOfN 函数。
具化 Prop 数据类型
我们完善了不少关于生成器的定义信息，然后把目光放回到 Prop 上来：
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)6
Prop 似乎还缺少了一点信息。尽管 SuccessCount 表示了成功测试数目，但它不知道多少个成功的测试才算通过。我们仍然需要显示指定一个数值 TestCases。显然，在测试完全通过的情况下，SuccessCount == TestCases。在这种情况下，我们反而不再需要关注 SuccessCount 的数目了。
因此，不妨将 check 方法的 Either 类型替换成 Option[(FailedCase,SuccessCount)]。当测试没有完全通过时，返回 Some((FailedCase,SuccessCount))；当测试全部通过时，返回 None。
这看起来有点别扭。因为根据以往的编程习惯，我们通常用 Some 来表达正确的逻辑。对于 Option 而言，这种做法无可厚非，只是容易引起混淆。因此我们又一次将 Option[(FailedCase,SuccessCount)] 替代为代数数据类型 Result，由它派生出代表测试结果的 Falsified 和 Passed 类型，这样一来就很明了了。
这里使用了 Scala 3 语法的枚举类型。见笔者的这篇笔记：Scala 3 新特性一览 - 掘金 (juejin.cn)
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)7
下面是兼容 Scala 2 语法的 Result 声明方式：
val xs = Gen.listOf(Gen.choose(0,100))// 验证 xs 的性质满足：// 1. 两次倒序排列等于它自身。// 2. xs 的首元素等于倒序排列后的尾元素。val prop = forAll(xs)(ns => ns.reverse.reverse == ns) && forAll(xs)(ns => ns.headOption == ns.reverse.lastOption)8
这些足够去表现 Prop 吗？我们再来看看其定义的 forAll 方法：
def forAll[A](a : Gen[A])(f : A => Boolean) : Prop
forAll 还是没有办法直接获取一个 A 参数。想要从 Gen[A] 那里获取 A 参数，我们就必须主动提供一个生成器 RandomGen。不妨先将这个生成器的依赖添加到 Prop 的 run 方法上：
def listOf[A](a : Gen[A]) : Gen[List[A]]0
假设还需要其它依赖，我们也暂时全部加到 run 的入参里。现在，forAll 函数就有足够的线索去实现了。
object Prop: type SuccessCount = Int type TestCases = Int type FailedCase = String enum Result(isFalsified$ : Boolean) : val isFalsified :Boolean = isFalsified$ case Falsified(failures: FailedCase,successes: SuccessCount) extends Result(true) case Passed extends Result(false) def forAll[A](a : Gen[A])(f : A => Boolean) : Prop = Prop { (n,rdmGen) => { import Result.* randomStream(a)(rdmGen).zip(LazyList.from(0)).take(n).map { case (a, i) => try { if(f(a)) Passed else Falsified(a.toString,i) } catch { case e : Exception => Falsified(buildMsg(a,e),i)} }.find(_.isFalsified).getOrElse(Passed) } } // 2.13 版本中，Stream 已被 LazyList 替代。 def randomStream[A](g : Gen[A])(rdmGen : RandomGen) : LazyList[A] = val (item,nxg) = g.state.run(rdmGen) item #:: randomStream(g)(nxg) def buildMsg[A](a : A, e : Exception) : String = s""" |test case: ${a} generated an exception: ${e.getMessage} |stack trace =>> |${e.getStackTrace.mkString("\n")} |""".stripMargin 除了 forAll 方法之外，这里还额外实现了两个辅助函数 randomStream 和 buildMsg。其中，randomStream 是一个共递归 ( 或称守护递归 )。它通过一个懒加载的 LazyStream 源源不断地用生成器生成元素，笔者曾在这一章提到过：探究 Scala 非严格求值与流式数据结构 - 掘金 (juejin.cn)。buildMsg 则是一个字符串模板，当测试失败时反馈信息。
forAll 内部捕获所有可能的异常并转换为测试失败。
基于现在的 Prop 的定义，我们可以实现组合版本的 && 和 || 了，这两个方法均具备 短路 特性。
def listOf[A](a : Gen[A]) : Gen[List[A]]2
注意，在失败的场景下，我们无法定位到那个出错的 Prop。因此，最好设置一个标签机制，同时又不需要对代码结构做过多更改。但这部分不是最核心的设计部分，为了代码的简洁性，这里暂时不做考虑。
到目前为止，这些简易的 API 已经足够用作一个 mini 版 ScalaCheck 了。在下文的例子中，我们结合 Gen.listOfN 和 Gen.choose 函数去指示程序生成长度为 5 的，元素值域为 [0,100) 的序列生成器 Gen[List[Int]]。然后，通过 forAll 传入这个生成器和相应的谓词："检查是否所有的数都小于 10"。同时，在 run 的参数中设置：
指定测试次数，这里设置为 1。
一个用于启动生成器的随机数生成工具 new SimpleRandom(999L)，它继承于 RandomGen。
从概率上来看，这个测试极有可能失败，程序会将导致测试失败的序列 List[Int] 打印到终端。
def listOf[A](a : Gen[A]) : Gen[List[A]]3
最小化测试样例
我们在前文提到了最小化测试样例的方法。在理想的条件下，我们的框架能够找到最小测试集，或者是导致失败的最小测试集，以便更好的暴露问题。通常这有两条路线：
收缩 —— 在发现导致失败的测试用例之后，再运行一个独立的过程，不断缩小测试的区间直到没有失败。这通常都要额外编码来实现。
定长生成 —— 与其在事后收缩，不妨在一开始逐步增加测试的区间和复杂度。这种想法可以用各种拓展方式使得测试在合理的范围内做大幅的跳跃。
无论是 ScalaCheck 还是 Haskell 的 QuickCheck 都是使用第一种思路去实现的，这没有什么不好，这里只是出于简单的目的，这里选择另一种方式去实现。在不改变 Gen 本身的定义的前提下，我们创建一个 SGen，它自身就是一个携带区间长度信息的生成器。
def listOf[A](a : Gen[A]) : Gen[List[A]]4
现在可以实现一个无需显式指定生成长度 n 的 listOf 方法：
def listOf[A](a : Gen[A]) : Gen[List[A]]5
我们看看 SGen[A] 类型是如何影响着 Prop 性质类型及其 forAll 方法的。forAll 方法的签名如下：
def listOf[A](a : Gen[A]) : Gen[List[A]]6
目前来看，这个函数不可能实现。SGen 需要被告知测试的最大长度 max 的，但是目前的 Prop 却没有提供任何线索。和之前那样，这里仅简单地将长度信息补充到 Prop 的构造器内部。这是最容易想到的，但事实上并不是好的设计，因为不是每一处 Prop 的构建都需要这个字段。
我们重写了一个基于 SGen[A] 的版本。如下：
def listOf[A](a : Gen[A]) : Gen[List[A]]7
该版本的 forAll 会创建总共 max * eachBatch 个测试用例。在此期间，程序会逐步创建长度从 0 到 max - 1 的序列进行测试；每个长度的序列会被重复测试 eachBatch 次，并作为一个 prop。所有的 prop 通过 && 串接起来，作为一个总体的性质被测试。
不是每一处创建的 Prop 都需要接受 max 参数，因此部分参数使用 _ 或者 __ 忽略掉了。另一个要点则是，整个 forAll 方法只使用一个随机数生成器生成序列元素。
提高 API 的易用性
帮助函数
用于定长生成测试的 API 实现得差不多了。下面是 SGen 配合 forAll 的简单调用，SGen[List[Int]] 现在抽象出了一个已知值域但长度未知的序列。
def listOf[A](a : Gen[A]) : Gen[List[A]]8
直接调用现有的 API 还是有点麻烦。将 "生成性质，检验结果" 的逻辑封装到一个过程内部会更好，这里将其命名为 run 方法。预设好参数的默认值，可以让 run 方法变得更加易用。
def listOf[A](a : Gen[A]) : Gen[List[A]]9
下面是使用 run 实现的上述测试。即便用户想要自行指派参数，也可以通过补充隐式参数列表的方式来简单实现：
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]0
证明性质
我们曾在之前的并行计算示例中发现了 映射法则，见 Scala 纯函数式库设计：并行编程 - 掘金 (juejin.cn)。如：
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]1
对这个法则的验证是否可以使用现在的 API 表达呢？当然可以，只不过写起来有点丑：
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]2
forAll 对于这个例子而言通用性太强了。这里只需要一个硬编码的例子，并且能够肯定只要这一个特例通过，那么无论再换成什么值也肯定没问题。这种情况称性质被证明 ( proved )了。对于这样的测试，我们不需要额外指定列表最大长度，测试数量 ( 只要测试一次就足够了)，以及生成器，因此在如下的 check 函数中，这些参数都被 _ 简单地忽略掉了。
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]3
同时，我们还可以添加一个数据结构 Proved，将被证明的情形和 Passed 做稍许区分。
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]4
此外还需要稍微修改 && 的实现 ( || 只关注 Falsified 类型，因此不需要改动 )。Scala 3 提供了并类型 ( Union Type )，因此修改起来十分简单：
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]5
关于 Scala 3 的知识，可以回顾：Union Types (scala-lang.org)。有了 check 函数之后，上例的测试表达方式变得更加简单了：
// 证明 1 个性质。run{ forAll(Gen.unit(Par.unit(1))){ i => i.map(_ + 1)(exec).get == Par.unit(2)(exec).get }}// 证明 2 个性质。run { check{ def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]1() } && check { Par.unit(2).map(_ + 1)(exec).get == Par.unit(3)(exec).get() }}关于共同的模式
有没有发现我们实现的 Gen 和之前定义过的 Par，State，Option 乃至 Future 都十分相似？比方说，我们在 Gen 上定义了：
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]7
flatMap 方法也在这些定义类中出现过，只不过具体的类型存在少许不同：
def listOfN[A](n : Int, a : Gen[A]) : Gen[List[A]]8
这意味着这些类型虽然有不同语义，但是在底层却满足同样的法则。换句话说，在软件世界里看似不同的问题，它们的函数式解决方案却为数不多。许多库本质上都是基础结构的简单组合，然后不断出现在不同的问题域里。
在下一章，我们将在另一个问题域中讨论函数式编程的场景 —— 解析。比如说，实现一个 JSON 的语法解析器。熟悉模式依旧会出现。
原文：https://juejin.cn/post/7102399429650415653