示例工程【免费下载链接】fpinscalaCode, exercises, answers, and hints to go along with the book Functional Programming in Scala项目地址https://gitcode.com/gh_mirrors/fp/fpinscala点击查看免费下载导读本文围绕《Functional Programming in Scala》配套仓库 fpinscala 的 state 章节练习 8 答案 展开完整剖析两个核心问题如何用flatMap把显式传递 RNG 状态的组合方式抽象成可复用的组合子以及如何用拒绝采样rejection sampling实现无模偏差的nonNegativeLessThan(n)。读完本文你将掌握状态传递计算的本质、flatMap与map在组合能力上的关键差异以及它在通用StateMonad 与糖果机模拟练习 11中的延伸应用。一、练习背景从map/map2到flatMap的演进在 fpinscala 第 6 章state包中随机数生成器被建模为纯函数式的状态计算。核心类型定义在 answers/state/State.scalatype Rand[A] RNG (A, RNG)即Rand[A]是接收一个RNG返回一个值A和下一个RNG状态的函数。之前的练习已经实现了unit、map、map2、sequence等组合子例如 map2 的实现 将初始 RNG 依次传递给两个子计算并串联状态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)但map与map2都要求后续计算不依赖前一个计算的结果map只能对结果做纯变换map2只能把两个独立计算的结果合并。一旦出现下一步的随机计算取决于上一步取到的值这种需求例如根据nonNegativeInt的结果决定是否重试就需要一个更强的组合子——这就是练习 8 引入flatMap的原因。二、核心答案一flatMap的实现练习 8 的答案 给出了flatMap的实现def flatMapA, B(f: A Rand[B]): Rand[B] rng0 val (a, rng1) r(rng0) f(a)(rng1)逐行拆解其工作原理r: Rand[A]先运行第一个状态计算从初始状态rng0得到结果值a与后继状态rng1f(a)(rng1)把上一步的结果a交给函数ff返回一个全新的Rand[B]即依赖于a的下一步计算再用上一步传递下来的状态rng1去运行它。与map相比关键差异在于map中变换函数f: A B是纯值函数无法拿到新的状态而flatMap中f: A Rand[B]可以构造出全新的状态计算因此能实现计算流程随上一步结果动态分支。对应 练习 8 的提示 也点明了这一点使用flatMap的实现几乎与之前尝试用map实现而失败的版本一模一样——它们都先运行r取出(a, rng1)区别仅在于下一步是把a交给map的纯函数还是交给flatMap的返回新计算的函数。该答案在 答案源码 中完整保留并且 RNGSuite 测试 直接以练习 8 的nonNegativeLessThan作为flatMap的验证用例。三、核心答案二nonNegativeLessThan与模偏差问题3.1 为什么不能直接用取模一个自然的直觉是从nonNegativeInt取到非负整数i后用i % n得到[0, n)范围内的结果。但这样做会引入模偏差modulo biasnonNegativeInt的取值范围是[0, Int.MaxValue]当n不能整除Int.MaxValue 1时较小的余数会比更大的余数出现得更频繁。例如n 3时Int.MaxValue 1 2147483648而2147483648 % 3 2导致余数0和1各多出一次出现机会生成结果并非均匀分布。3.2 拒绝采样方案练习 8 的答案 采用拒绝采样消除偏差def nonNegativeLessThan(n: Int): Rand[Int] flatMap(nonNegativeInt): i val mod i % n if i (n-1) - mod 0 then unit(mod) else nonNegativeLessThan(n)理解这段代码的关键在于边界判定条件i (n - 1) - mod 0mod i % n所以i - mod是n的整数倍代表i所在整块区间的起始值当i - mod (n - 1) Int.MaxValue时说明以i - mod为起点、长度为n的完整区间仍落在nonNegativeInt的取值范围内此时i % n的分布是均匀的可以放心接受当该区间跨越了Int.MaxValue的边界即i落在最后一个不完整的块中时则拒绝本次结果递归调用nonNegativeLessThan(n)重新生成直到落在完整区间内为止。注意这里的递归是运行时动态发生的由于flatMap让后续计算依赖前值i是否落入拒绝区域只有在运行时才能知道这正是map/map2无法表达、必须由flatMap提供的分支能力。3.3unit(mod)的作用接受分支使用unit(mod)返回结果def unitA: Rand[A] rng (a, rng)unit是不改变状态的恒等计算把mod作为结果返回同时原封不动地透传rng1。由于flatMap已经把状态串联起来unit保证了拒绝/接受两种分支最终都产出(Int, RNG)类型的结果类型上完全统一。四、源码佐证flatMap在答案库中的完整形态练习 8 的答案在 answers/state/State.scala 中与后续练习的答案连成一条完整的演进链def flatMapA, B(f: A Rand[B]): Rand[B] rng0 val (a, rng1) r(rng0) f(a)(rng1) def nonNegativeLessThan(n: Int): Rand[Int] flatMap(nonNegativeInt): i val mod i % n if i (n-1) - mod 0 then unit(mod) else nonNegativeLessThan(n)紧接着的 练习 9 答案 展示了flatMap的通用性——一旦有了它map和map2都可以用它重新表达def mapViaFlatMapA, B(f: A B): Rand[B] flatMap(r)(a unit(f(a))) def map2ViaFlatMapA, B, C(f: (A, B) C): Rand[C] flatMap(ra)(a map(rb)(b f(a, b)))这说明flatMapunit是比map/map2更底层、表达能力更强的原始组合子——这正是 Monad 结构在状态计算中的自然浮现。从源码结构可以推断练习 8 是第 6 章从手动传递 RNG走向通用StateMonad的转折点。五、延伸从Rand到通用StateMonad练习 8 中Rand[A] RNG (A, RNG)与某个具体状态类型RNG绑定但flatMap/unit的实现根本不关心状态的具体类型。答案源码随即把它抽象为对任意状态S都适用的 opaque type Stateopaque type State[S, A] S (A, S)其flatMap与练习 8 的实现结构完全一致State.scala#L161-L164def flatMapB: State[S, B] s val (a, s1) underlying(s) f(a)(s1)Rand[A]可以看作State[RNG, A]的特例。练习 11 的糖果机模拟正是这个通用State的典型应用11.answer.mdsimulateMachine用State.traverse串联一系列State.modify(update(i))更新操作最后用State.get读取最终机器状态完全隐藏了状态的手动传递。六、测试验证拒绝采样与 flatMap 的正确性保障仓库中的 RNGSuite 对练习 8 的两个答案提供了属性测试test(RNG.flatMap)(genRNG ** genCounter ** genSmallPosNum): case rng ** counter ** limit def nonNegativeLessThan(n: Int): Rand[Int] flatMap(nonNegativeInt): i val mod i % n if (i (n - 1) - mod 0) unit(mod) else nonNegativeLessThan(n) assert(checkRNGNonNegativeLessThan(rng, counter, nonNegativeLessThan(limit), limit))其中checkRNGNonNegativeLessThanRNGSuite.scala#L129-L137以tailrec循环生成大量样本逐一断言结果严格落在[0, limit)区间内private def checkRNGNonNegativeLessThan(rng: RNG, counter: Int, generate: Rand[Int], limit: Int): Boolean tailrec def loop(rng: RNG, counter: Int): Boolean counter 0 || { val (i, rng2) generate(rng) if 0 i i limit then loop(rng2, counter - 1) else fail(sThe generated value $i isnt in the interval [0, $limit).) } loop(rng, counter)这套测试还贯穿了更宏观的验证思路RNGSuite中多个测试通过checkRND检查连续生成的随机值互不重复间接佐证了flatMap串联状态时不会复用同一个 RNG 导致重复输出。而 CandySuite 则验证了StateMonad含traverse、modify、get在糖果机场景下的行为投币解锁、转动出货、缺糖时忽略所有输入等从应用层确认了flatMap组合能力的正确落地。若想亲自运行这些验证可在仓库根目录执行scala-cli test . -- fpinscala.exercises.state.*七、小结练习 8 在 fpinscala 第 6 章中承担着承上启下的角色flatMap的引入解决了后续状态计算依赖前值的表达瓶颈其实现不过是r(rng0)取结果与状态、再交给f用新状态继续运行——比map只多了一层返回新计算的间接性正如 练习 8 提示 所言与失败版的map实现几乎相同nonNegativeLessThan用拒绝采样消除了i % n的模偏差边界判定i (n-1) - mod 0精确刻画了完整区间的接受条件而递归拒绝分支必须借助flatMap的动态分支能力才能表达抽象层次的跃迁从Rand到通用State为后续 Monad 章节和糖果机模拟铺平了道路。建议读者对照 练习文件 自行实现flatMap与nonNegativeLessThan再用scala-cli test . -- fpinscala.exercises.state.RNGSuite验证实现体会先失败于 map、后用 flatMap 成功的完整思考路径。赞分享示例工程【免费下载链接】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 第 3 章练习 20 精解用 map 与 concat 组合实现 List.flatMapfpinscala 第 3 章练习 20 精解用 map 与 concat 组合实现 List.flatMap 本文聚焦于《Functional Progra示例工程fpinscala 错误处理章节练习 6 精解为 Either 实现 map、flatMap、orElse 与 map2fpinscala 错误处理章节练习 6 精解为 Either 实现 map、flatMap、orElse 与 map2 本文以 fpinscala 仓库《F示例工程创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考