示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载本篇技术指南围绕 fpinscala 仓库《Functional Programming in Scala》一书的配套练习与答案库第 6 章 state 章节的练习 4 展开深入讲解如何在纯函数式风格下实现ints给定数量count与随机数生成器RNG一次性产出一串随机Int。通过对照仓库中的练习文件、标准答案与属性测试源码你将掌握显式状态传递state threading这一核心范式理解普通递归与尾递归两种写法的差异、列表构造顺序的微妙之处并看到它如何被后续的Rand/sequence抽象所取代。一、练习背景为什么随机数生成必须手动传状态在进入ints之前需要先理解第 6 章确立的纯函数式随机数生成模型。该章的练习骨架位于 src/main/scala/fpinscala/exercises/state/State.scala其中定义了核心抽象trait RNG: def nextInt: (Int, RNG) // Should generate a random Int.关键点在于nextInt不返回单个整数而是返回一个二元组(Int, RNG)——既包含生成的伪随机整数又包含下一个随机数生成器状态。这样做的目的是保持纯函数pure function与引用透明性referential transparency同一个RNG实例调用nextInt永远得到相同结果不会像java.util.Random那样悄悄修改内部可变状态。仓库中给出的具体实现是经典的线性同余生成器LCG见 src/main/scala/fpinscala/answers/state/State.scalacase class Simple(seed: Long) extends RNG: def nextInt: (Int, RNG) val newSeed (seed * 0x5DEECE66DL 0xBL) 0xFFFFFFFFFFFFL // is bitwise AND. val nextRNG Simple(newSeed) val n (newSeed 16).toInt // is right binary shift with zero fill. (n, nextRNG)由此ints的问题就具体化了想要连续生成count个随机整数就必须把每一次nextInt返回的新状态作为下一次调用的输入状态像链条一样串联下去——这一过程被称为显式状态传递。二、练习 4 的题目要求与答案原文练习 4 要求实现的函数签名在练习文件中以???占位见 src/main/scala/fpinscala/exercises/state/State.scala#L39def ints(count: Int)(rng: RNG): (List[Int], RNG) ???语义是生成一个长度为count的随机整数列表同时返回最终的状态RNG供后续继续生成使用。该练习的 hint 文件 answerkey/state/04.hint.md 中只有一个-表示没有提供提示需要自行推理——此时答案文件的价值就体现出来了。关联文档 answerkey/state/04.answer.md 给出了两种完整解法下面分别展开。三、解法一简单递归——按生成顺序逐个构造列表答案原文的第一种写法// A simple recursive solution def ints(count: Int)(rng: RNG): (List[Int], RNG) if count 0 then (List(), rng) else val (x, r1) rng.nextInt val (xs, r2) ints(count - 1)(r1) (x :: xs, r2)逐行拆解基准情形当count 0时不再生成任何数返回空列表List()并且原样返回传入的rng。注意这里用的是 0而不是 0意味着负数输入也安全——这一点与仓库测试中Gen.choose(-5, 20)的生成范围见下文测试章节完全对应。递归情形val (x, r1) rng.nextInt从当前状态rng取一个整数x得到新状态r1val (xs, r2) ints(count - 1)(r1)把r1而不是原来的rng传给递归调用继续生成剩余count - 1个整数得到列表xs与最终状态r2(x :: xs, r2)把本次生成的x用 cons 接到xs前面连同最终状态r2一起返回。这种写法的核心是严格串行传递状态rng → r1 → r2每一次nextInt都消费前一次产生的新状态从而保证序列不重复、可复现。由于先取x、再递归生成xs结果列表中的元素按生成顺序排列x1 :: x2 :: x3 :: ...。这份答案在仓库完整实现中位于 src/main/scala/fpinscala/answers/state/State.scala#L54-L61与练习文件中的占位签名一一对应可直接对照阅读。四、解法二尾递归——用累加器换取恒定栈空间答案原文的第二种写法// A tail-recursive solution def ints2(count: Int)(rng: RNG): (List[Int], RNG) def go(count: Int, r: RNG, xs: List[Int]): (List[Int], RNG) if count 0 then (xs, r) else val (x, r2) r.nextInt go(count - 1, r2, x :: xs) go(count, rng, List())逐行拆解在外部函数ints2内部定义局部辅助函数go它额外携带一个累加器参数xs: List[Int]用于边走边攒已生成的整数基准情形count 0时直接把累加器xs与当前状态r返回递归情形取一个整数x与新状态r2后递归调用go自身并把xcons 进累加器x :: xs——递归调用是整个函数体的最后一个动作因此这是真正的尾递归tail recursionScala 编译器可将其优化为循环栈深度恒定不会因count很大而栈溢出。这里有一个值得注意的细节累加器版本的列表顺序与生成顺序相反。以count 3为例执行轨迹为取x1go(2, r2, x1 :: Nil)取x2go(1, r3, x2 :: x1 :: Nil)取x3go(0, r4, x3 :: x2 :: x1 :: Nil)→ 返回[x3, x2, x1]。即先取出的数反而排在列表末尾。这一现象与答案文件在sequence注释中讨论的foldRight/foldLeft顺序问题如出一辙见 src/main/scala/fpinscala/answers/state/State.scala#L111-L119若对输出顺序有要求通常的做法是结束时对累加器做一次reverse。而仓库的测试只校验值互不相同不校验顺序因此两种写法在测试视角下是等价的。五、两种解法对比何时选用哪一种维度简单递归ints尾递归ints2结果顺序与生成顺序一致x1 :: x2 :: ...与生成顺序相反累加器 cons 所致栈空间O(count)随输入线性增长O(1)编译器可优化为循环时间/堆空间O(count)结果列表本身占 O(count)同左可读性直接、贴近逐次生成的直觉需理解累加器技巧边界处理count 0返回空列表与原始rng同左两条经验法则追求栈安全count可能很大时优先尾递归版本并可用tailrec注解让编译器强制校验仓库测试辅助函数checkRND就使用了import scala.annotation.tailrec见 src/test/scala/fpinscala/exercises/state/RNGSuite.scala#L10追求结果顺序自然时用简单递归或在尾递归版本末尾补一次reverse。无论哪种写法都必须恪守同一原则每轮生成只使用上一轮返回的新RNG状态绝不能重复使用旧状态否则会产生重复序列。六、仓库测试如何验证 ints 的正确性练习的验证依托属性测试框架PropSuite针对ints的测试位于 src/test/scala/fpinscala/exercises/state/RNGSuite.scala#L55-L58test(RNG.ints)(genRNG ** genCounter ** genLengthOfList): case rng ** counter ** lengthOfList if lengthOfList 0 then assert(ints(lengthOfList)(rng)._1.isEmpty) else assert(checkRND(rng, counter, ints(lengthOfList), list list list.distinct))它覆盖了两个关键性质负数与零输入genLengthOfList Gen.choose(-5, 20)见 RNGSuite.scala#L15当lengthOfList 0时断言结果列表为空——这正是答案中count 0基准情形要保证的值互不重复对正数长度用辅助函数checkRND连续跑counter轮断言list list.distinct即列表内没有重复元素。由于每次生成都消费新状态这个性质得以成立。在仓库根目录README 的构建说明见 README.md#L62-L96可以用 Scala CLI 单独运行该包的所有测试$ scala-cli test . -- fpinscala.exercises.state.*注意仓库设计上未完成练习时测试会失败stub 为???完成后即可通过。七、延伸从手写状态传递到 sequence 抽象ints的手工实现暴露了一个明显的痛点每次都不得不在代码里显式携带rng变量并层层传递正如上一题 answerkey/state/03.answer.md 末尾的注释所感叹的——There is something terribly repetitive about passing the RNG along every time.每次都把 RNG 传来传去实在太重复了。答案文件随后给出了解法先用类型别名抽象出Rand[A] RNG (A, RNG)再定义unit、map、map2最终用foldRight组合出sequence见 src/main/scala/fpinscala/answers/state/State.scala#L120-L128def sequenceA: Rand[List[A]] rs.foldRight(unit(Nil: List[A]))((r, acc) map2(r, acc)(_ :: _)) def _ints(count: Int): Rand[List[Int]] sequence(List.fill(count)(int))可以看到sequence内部正是以foldRight复刻了练习 4 中手写递归的构造逻辑_ :: _逐元素 cons而_ints一行即等价于ints的声明式版本。答案注释还点明sequence的实现从未直接谈论具体的RNG类型这是它能够进一步泛化为State[S, A]抽象opaque type见 State.scala#L146的强信号——同样的foldRightmap2模式在State.sequence中原样复用State.scala#L171-L172并最终支撑起糖果机模拟simulateMachine等更复杂的应用。因此练习 4 的ints不仅是随机数生成的一个实用工具更是理解显式状态传递 → Rand 组合子 → 通用 State 抽象这条抽象化主线的关键一步。掌握它的递归与尾递归两种写法也就掌握了第 6 章后续所有内容的地基。赞分享示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载相关推荐fpinscala 练习精解用 Scala 3 尾递归实现斐波那契数列第 2 章 Exercise 1fpinscala 练习精解用 Scala 3 尾递归实现斐波那契数列第 2 章 Exercise 1 导读 本文围绕 fpinscala 仓库第 2 章示例工程fpinscala 练习精讲用多态函数与尾递归实现 isSorted 有序性检测第 2 章练习 2 详解fpinscala 练习精讲用多态函数与尾递归实现 isSorted 有序性检测第 2 章练习 2 详解 本文以 answerkey/gettingsta示例工程fpinscala 第 3 章练习 23 精解用模式匹配与尾递归实现 List 的 zipWithfpinscala 第 3 章练习 23 精解用模式匹配与尾递归实现 List 的 zipWith 本文以 fpinscala 仓库中 answerkey/d示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考