示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载本文以 fpinscala 仓库第 6 章state练习 06 的官方提示与答案为骨架深入讲解如何在纯函数式随机数生成器RNG之上实现map2组合子重点剖析把哪个 RNG 传给哪个参数、以什么顺序传递这一核心设计决策并结合仓库源码与属性测试说明如何验证实现行为。读完本文你将掌握状态线程化组合子的实现套路、三种 RNG 传递方案的后果对比以及如何用属性测试守住行为边界。练习背景Rand 与状态线程化第 6 章state的核心主题是用纯函数管理状态。练习 06 所在的state章节在仓库中的目录结构如下练习骨架src/main/scala/fpinscala/exercises/state/State.scala所有待补全的???都在这份文件里完整答案src/main/scala/fpinscala/answers/state/State.scala同一章节所有习题的参考实现官方提示与答案answerkey/state/目录下的06.hint.md与06.answer.md练习的起点是一个纯函数式的随机数生成器trait RNG: def nextInt: (Int, RNG) // Should generate a random Int.其参考实现Simple是一个典型的线性同余生成器LCG见 answers/state/State.scalacase class Simple(seed: Long) extends RNG: def nextInt: (Int, RNG) val newSeed (seed * 0x5DEECE66DL 0xBL) 0xFFFFFFFFFFFFL val nextRNG Simple(newSeed) val n (newSeed 16).toInt (n, nextRNG)关键点在于nextInt是纯函数——同一个种子必然产生同一个整数因此必须把新的种子即新的RNG显式返回出来供下一次调用使用。这种每次调用都把状态显式传下去的写法就是函数式编程里常说的状态线程化state threading。为了让状态传递不那么啰嗦仓库定义了一个类型别名type Rand[A] RNG (A, RNG)Rand[A]本质上是一个函数接收 RNG返回值 A新的 RNG。在此基础上前面几个练习已经实现了int、unit、map等基本组合子见 answers/state/State.scala。练习 06 要做的就是把两个Rand组合起来。练习 06 的目标map2 的类型签名与语义练习骨架中对应的待补全函数位于 exercises/state/State.scaladef map2A, B, C(f: (A, B) C): Rand[C] ???它的语义很直观给定两个随机动作ra和rb先用ra生成一个A再用rb生成一个B最后用纯函数f把两者合并成C整体仍然是一个Rand[C]。map2的价值在于它让两个随机动作的组合可以被当作一个整体来复用。后续练习中的sequence、both、randIntDouble等组合子几乎都建立在map2之上。官方提示逐句解读06.hint.md练习 06 的官方提示全文如下Start by accepting an RNG. Note that you have a choice in which RNG to pass to which function, and in what order. Think about what you expect the behavior to be, and whether your implementation meets that expectation.这句话浓缩成三个递进的要点1. Start by accepting an RNG从接受一个 RNG开始map2的返回类型是Rand[C]也就是RNG (C, RNG)。因此实现的第一步永远是写出rng0 // 从这里开始拆解所谓接受一个 RNG就是先把这个入参rng0写出来作为整个状态线程化的起点。2. You have a choice in which RNG to pass to which function, and in what order把哪个 RNG 传给哪个函数、以什么顺序传你有选择这是本练习最核心的教学点。实现过程中你会面临至少三种方案详见下一节提示提醒你这不是一道只有一个标准答案的题你的选择会直接影响行为。3. Think about what you expect the behavior to be, and whether your implementation meets that expectation想清楚你期望的行为并检查实现是否满足写完实现后要主动问自己我期望map2(int, int)产生什么我的实现真的满足了吗这一步把能编译与行为正确区分开来也是后续属性测试的思维起点。三种 RNG 传递方案对比假设现在要组合两个随机动作ra和rb初始 RNG 为rng0。你面临的选择是rng0到底给谁中间产生的新 RNG 又给谁方案 A顺序传递标准答案rng0 val (a, rng1) ra(rng0) // rng0 给第一个动作 val (b, rng2) rb(rng1) // 产生的新 RNG 给第二个动作 (f(a, b), rng2)这是 06.answer.md 给出的实现也是绝大多数情况下的推荐写法状态像接力棒一样从rng0传到rng1再传到rng2每个动作都在自己独有的随机数序列上取值。方案 B反序传递rng0 val (b, rng1) rb(rng0) // 先把 rng0 给 rb val (a, rng2) ra(rng1) // 再把新 RNG 给 ra (f(a, b), rng2)答案注释里明确说Its not necessarily wrong to do this the other way around, since the results are random anyway.——因为结果本来就是随机的a和b的生成顺序调换并不会破坏正确性只是消费随机数序列的顺序不同。从行为可预期的角度看两种方案都是合理的。方案 C同源传递陷阱rng0 val (a, rng1) ra(rng0) // rng0 给 ra val (b, _) rb(rng0) // 同一个 rng0 再给 rb (f(a, b), rng1)这是最容易写错、也最能暴露问题的一种把同一个初始 RNG 同时传给ra和rb。由于RNG是纯函数ra(rng0)与rb(rng0)在ra rb时必然产生完全相同的值。答案注释点出了后果E.g. if both arguments areRNG.intthen we would always get two of the sameIntin the result.也就是说map2(int, int)((a, b) (a, b))会永远返回(n, n)——两个相同的整数。这显然与生成两个独立的随机数的直觉期望相悖。更隐蔽的问题是这种写法还把状态进度丢了rb本应消费rng1继续推进序列结果却回退到rng0重新开始。答案实现逐行剖析06.answer.md官方答案及其完整注释如下原文一字未删// This implementation of map2 passes the initial RNG to the first argument // and the resulting RNG to the second argument. Its not necessarily wrong // to do this the other way around, since the results are random anyway. // We could even pass the initial RNG to both f and g, but that might // have unexpected results. E.g. if both arguments are RNG.int then we would // always get two of the same Int in the result. When implementing functions // like this, its important to consider how we would test them for // correctness. def map2A, B, C(f: (A, B) C): Rand[C] rng0 val (a, rng1) ra(rng0) val (b, rng2) rb(rng1) (f(a, b), rng2)逐行拆解def map2A, B, C(f: (A, B) C): Rand[C]—— 柯里化签名先接收两个随机动作再接收合并函数。之所以把f放在第二个参数列表是为了方便局部应用例如map2(double, double)(_ _)。rng0 —— 返回一个函数入参就是接受的那个 RNG与提示第一句呼应。val (a, rng1) ra(rng0)—— 把初始 RNG 交给第一个动作同时解出值a和新状态rng1。val (b, rng2) rb(rng1)—— 把新状态rng1交给第二个动作绝不复用rng0。(f(a, b), rng2)—— 合并结果并把最终状态rng2一并返回保证状态线程化不断裂。值得注意的是这个实现与答案中sequenceanswers/state/State.scala的配合sequence用foldRight反复调用map2把列表里的Rand逐个串起来之所以顺序不反正是因为在map2内部状态是从左到右传递的def sequenceA: Rand[List[A]] rs.foldRight(unit(Nil: List[A]))((r, acc) map2(r, acc)(_ :: _))如果map2采用方案 B反序sequence的结果列表顺序就会受影响——这再次印证了顺序选择会扩散到整个组合子体系这一事实。用测试验证期望行为答案注释最后一句点明了方法论its important to consider how we would test them for correctness。仓库中的属性测试正好为我们演示了这一点。RNG.map2 的测试不允许出现相同的两个值在 src/test/scala/fpinscala/exercises/state/RNGSuite.scala 中map2的测试直接针对了同源传递陷阱test(RNG.map2)(genRNG ** genCounter): case rng ** counter val randC map2(double, double)((d1, d2) (d1, d2)) assert(checkRND(rng, counter, randC, (d1, d2) isInInterval(d1) isInInterval(d2) d1 ! d2))这里用map2(double, double)组合两个相同的随机动作然后断言两个值都在[0, 1)区间内isInInterval两个值不相等d1 ! d2。这条d1 ! d2断言正是对方案 C同源传递的定向打击如果实现错误地把同一个 RNG 传给两个double测试就会稳定失败。它把行为期望翻译成了可机器执行的属性。测试底层的checkRNDRNGSuite.scala还会额外检查连续两次生成的值不能相同进一步保证随机数序列真的在推进private def checkRNDA: Boolean tailrec def loop(rng: RNG, counter: Int, previousValue: Option[A] None): Boolean counter 0 || { val (value, rng2) generate(rng) if !isCorrect(value) then fail(sThe generated value $value is invalid.) else if previousValue.contains(value) then fail(sThe RNG generated two identical values in a row ($value).) else loop(rng2, counter - 1, Some(value)) } loop(rng, counter)State.map2 的测试状态推进两步map2的思想不止用于Rand。在同一个章节中State类型上的map2answers/state/State.scala用for推导实现了同样的状态线程化def map2B, C(f: (A, B) C): State[S, C] for a - underlying b - sb yield f(a, b)对应的测试在 src/test/scala/fpinscala/exercises/state/StateSuite.scalatest(State.map2)(genStringList): list val (c, s) stateA.map2(stateB)(printResult).run(list) // a - the result of the initial state, b - the result of the next state val expectedC printResult(list.headOption, list.drop(1).length) // s - the result of passing through two states (after a and b) assertEquals(c, expectedC) assertEquals(s, list.drop(2))其中stateA取列表头部、stateB计算剩余长度两者各自消费一步状态最终状态断言为list.drop(2)——这精确验证了状态按顺序推进了两步的期望与map2内部ra(rng0)→rb(rng1)的传递逻辑完全一致。如果想在本地运行 state 章节的测试仓库 README 提供了 scala-cli 命令按包名过滤即可详见 README.mdscala-cli test . -- fpinscala.exercises.state.*注意仓库默认状态下练习骨架是???所以未完成的习题对应测试会失败随着你逐个实现练习测试会逐步转绿。这正是仓库设计成练习驱动的原因。延伸map2 在组合子体系中的位置map2并非孤立存在它是整个状态组合子大厦的基石之一both与randIntDoubleboth(ra, rb)就是map2(ra, rb)((_, _))用于把两个随机动作打包成一个元组动作answers/state/State.scala。sequence如前述sequence用foldRightmap2把List[Rand[A]]串成Rand[List[A]]L120-L121。map2ViaFlatMap一旦有了flatMapmap2可以退化定义出来flatMap(ra)(a map(rb)(b f(a, b)))L143-L144。这说明map2是flatMap与map的组合特例也预示了第 11 章 Monad 的抽象。State.sequence/State.traverse在更一般的State[S, A]上同样的模式支撑起糖果机模拟器Candy.simulateMachine的实现L192-L197即用State.traverse(inputs)(i State.modify(update(i)))依次处理投币与转动旋钮的输入序列。因此练习 06 虽小却直接关系到你对后续sequence、flatMap乃至 Monad 抽象的理解——理解 RNG 传递顺序就是理解状态线程化这一贯穿全书的主题。小结map2的实现第一步是接受一个 RNG第二步是决定 RNG 的传递顺序三种方案中顺序传递初始 RNG 给第一个动作、新 RNG 给第二个动作是标准答案反序传递不破坏随机正确性而同源传递会让map2(int, int)永远产出两个相同的整数是必须避免的陷阱判断实现是否正确的关键是明确行为期望期望独立随机性就用d1 ! d2这样的属性测试把它固化下来参见 RNGSuite.scalamap2是sequence、both、map2ViaFlatMap以及State泛化版本的基础理解它对理解整章乃至后续 Monad 章节都有直接帮助。参考文件索引官方提示 answerkey/state/06.hint.md、官方答案 answerkey/state/06.answer.md、练习骨架 exercises/state/State.scala、完整答案 answers/state/State.scala、相关测试 RNGSuite.scala 与 StateSuite.scala。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐fpinscala 状态章节练习解析用 flatMap 重新实现 map 与 map2Rand/State 第 6 章fpinscala 状态章节练习解析用 flatMap 重新实现 map 与 map2Rand/State 第 6 章 导读 本篇文章围绕《Functio示例工程fpinscala 练习精讲用多态函数与尾递归实现 isSorted 有序性检测第 2 章练习 2 详解fpinscala 练习精讲用多态函数与尾递归实现 isSorted 有序性检测第 2 章练习 2 详解 本文以 answerkey/gettingsta示例工程fpinscala 第 6 章状态传递精解intDouble、doubleInt 与 double3 组合随机生成器的实现原理fpinscala 第 6 章状态传递精解intDouble、doubleInt 与 double3 组合随机生成器的实现原理 导读 本文围绕 fpinsca示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考