• 示例工程

导读

本文围绕《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.scala：

type 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)

逐行拆解其工作原理：

1. r: Rand[A]：先运行第一个状态计算，从初始状态rng0得到结果值a与后继状态rng1；
2. f(a)(rng1)：把上一步的结果a交给函数f，f返回一个全新的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 bias）：nonNegativeInt的取值范围是[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 >= 0：

• mod = 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)))

这说明flatMap+unit是比map/map2更底层、表达能力更强的原始组合子——这正是 Monad 结构在状态计算中的自然浮现。从源码结构可以推断：练习 8 是第 6 章从"手动传递 RNG"走向"通用StateMonad"的转折点。

五、延伸：从Rand到通用StateMonad

练习 8 中Rand[A] = RNG => (A, RNG)与某个具体状态类型RNG绑定，但flatMap/unit的实现根本不关心状态的具体类型。答案源码随即把它抽象为对任意状态S都适用的 opaque type State：

opaque type State[S, +A] = S => (A, S)

其flatMap与练习 8 的实现结构完全一致（State.scala#L161-L164）：

def flatMapB: State[S, B] = s => val (a, s1) = underlying(s) f(a)(s1)

Rand[A]可以看作State[RNG, A]的特例。练习 11 的糖果机模拟正是这个通用State的典型应用（11.answer.md）：simulateMachine用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))

其中checkRNGNonNegativeLessThan（RNGSuite.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(s"The generated value '$i' isn't 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 成功"的完整思考路径。

• 示例工程