fpinscala 幺半群实战:用 Scala 3 given 定义积幺半群(productMonoid)
fpinscala 幺半群实战:用 Scala 3 given 定义积幺半群(productMonoid)
导读
本文以《Functional Programming in Scala》第 10 章(monoids)配套开源仓库 fpinscala 的练习 16 答案为核心,深入讲解如何用 Scala 3 的 given/using 机制把两个已有的 Monoid 组合成作用在二元组 (A, B) 上的积幺半群(product monoid)。读完本文,你将理解积幺半群的数学定义、given 实例的声明语法、它如何自动参与 Monoid 实例推导,以及它在 bag、mapMergeMonoid、functionMonoid 等复合幺半群场景中的实际应用,并通过仓库内的单元测试验证其满足幺半群定律。
一、背景:Monoid 抽象与本章练习脉络
fpinscala 仓库为书中每一章提供了练习桩(exercises)与完整答案(answers)两套源码。第 10 章幺半群对应的练习桩位于 exercises/monoids/Monoid.scala,完整答案位于 answers/monoids/Monoid.scala。
幺半群的核心抽象只有两个成员:
trait Monoid[A]:
def combine(a1: A, a2: A): A
def empty: A
一个合法的 Monoid[A] 必须满足两条定律:
- 结合律:
combine(a, combine(b, c)) == combine(combine(a, b), c) - 单位元:
combine(a, empty) == a且combine(empty, a) == a
本章练习从基础实例(intAddition、stringMonoid、optionMonoid 等)一路推进到 foldMap、foldMapV、parFoldMap,最终在练习 15–18 引入通过组合已有幺半群构造新幺半群的技巧:productMonoid(16)、functionMonoid(17)、mapMergeMonoid(18)。这正是本练习的核心价值所在:幺半群可以像积木一样组合,而 Scala 3 的 given 机制让这种组合可以被编译器自动发现并应用。
二、练习 16 答案:productMonoid 的完整实现
关联文档 answerkey/monoids/16.answer.md 给出的核心答案如下:
given productMonoidA, B: Monoid[(A, B)] with
def combine(x: (A, B), y: (A, B)) =
(ma.combine(x(0), y(0)), mb.combine(x(1), y(1)))
val empty = (ma.empty, mb.empty)
2.1 逐行拆解
| 代码片段 | 作用 |
|---|---|
given productMonoid[A, B] |
声明一个名为 productMonoid 的 given 实例(Scala 3 中的隐式值),可同时作用于任意类型 A、B |
(using ma: Monoid[A], mb: Monoid[B]) |
上下文参数:要求调用处能够自动解析出 Monoid[A] 与 Monoid[B] 两个实例,作为组合的“零件” |
: Monoid[(A, B)] with |
该实例的类型是作用在二元组 (A, B) 上的幺半群,with 开始实例体 |
def combine(x: (A, B), y: (A, B)) = (ma.combine(x(0), y(0)), mb.combine(x(1), y(1))) |
元组按分量逐一合并:第一分量用 ma.combine,第二分量用 mb.combine |
val empty = (ma.empty, mb.empty) |
单位元是各分量单位元的元组 |
其中 x(0) 与 x(1) 是 Scala 3 中对二元组 Tuple2 的按索引访问语法,等价于 x._1 与 x._2。
2.2 为什么说它是“积”幺半群
在代数中,两个幺半群 (A, ⊕, eA) 与 (B, ⊗, eB) 的笛卡尔积自然构成幺半群:载体为 A × B,二元运算定义为
(a1, b1) · (a2, b2) = (a1 ⊕ a2, b1 ⊗ b2)
单位元为 (eA, eB)。可以证明,只要两个分量各自满足结合律与单位元定律,组合后的元组运算同样满足这两条定律(证明思路:结合律逐分量成立,单位元逐分量成立,因此整体成立)。这就是“积幺半群”名称的由来,也是本答案在结构上完全照搬代数定义的体现。
2.3 实例化验证
在实际使用中,只要作用域里存在 Monoid[Int] 与 Monoid[String] 的 given 实例,编译器就会自动合成 Monoid[(String, Int)]:
// answers 源码中已提供这两个 given:
given Monoid[Int] with
def combine(x: Int, y: Int) = x + y
val empty = 0
// 自动推导:productMonoid[String, Int] 使用 stringMonoid + intAddition
val m = summon[Monoid[(String, Int)]]
m.combine(("a", 1), ("b", 2)) // ("ab", 3)
m.empty // ("", 0)
在 answers/monoids/Monoid.scala 中,given Monoid[Int] 与 given productMonoid 紧邻定义,正是为了说明:幺半群实例可以逐层叠加,productMonoid 站在 Monoid[Int] 等基础实例之上,自动成为作用域内可用的 Monoid[(A, B)]。
三、given/using:Scala 3 隐式机制的实战要点
本答案是全书较早完整使用 Scala 3 given/using 语法的示例,值得单独拆解:
given实例与val/def等价:given声明本质上是一个可以被编译器在隐式作用域中查找的实例,可以像val一样携带类型参数与上下文参数。using参数由编译器自动填充:(using ma: Monoid[A], mb: Monoid[B])意味着调用productMonoid时无需手写参数,编译器会从当前作用域、import的伴生对象等位置查找匹配的Monoid实例。- 嵌套组合能力:
productMonoid的using参数本身也可以是productMonoid,从而构造三元组、四元组乃至任意n元组的幺半群——例如Monoid[(A, (B, C))]。这种“实例之间互相组合”的递归结构,是驱动mapMergeMonoid等高级实例的基础。
作为对比,练习桩版本 exercises/monoids/Monoid.scala 保留了完全相同的签名,只把函数体留空(???),读者在完成练习 16 时只需补齐 combine 与 empty 两处实现:
given productMonoidA, B: Monoid[(A, B)] with
def combine(x: (A, B), y: (A, B)) = ???
val empty = ???
四、幺半群定律验证:测试与性质检验
4.1 仓库内的单元测试
在 MonoidSuite.scala 中,练习 16 的 productMonoid 有专门的测试:
test("Monoid.productMonoid")(genString ** genString ** genString ** Gen.int ** Gen.int ** Gen.int):
case a1 ** b1 ** c1 ** a2 ** b2 ** c2 =>
import Monoid.productMonoid
assertMonoid(productMonoid[String, Int], (a1, a2), (b1, b2), (c1, c2))
assertMonoid 工具方法(同文件 L169-L172)对任意三个样本 a, b, c 逐条断言结合律与左右单位元:
private def assertMonoidA: Unit =
assertEquals(m.combine(a, m.combine(b, c)), m.combine(m.combine(a, b), c), "associativity")
assertEquals(m.combine(a, m.empty), a, "identity")
assertEquals(m.combine(m.empty, a), a, "identity")
测试使用 Gen 随机生成字符串与整数组合,通过基于性质的测试(property-based testing)覆盖大量输入。
4.2 通用的 monoidLaws 性质
除了具体实例测试,本章还提供了不依赖具体类型的定律检验函数 monoidLaws(见 04.answer.md 与 answers/monoids/Monoid.scala):
def monoidLawsA: Prop =
val associativity = Prop
.forAll(gen ** gen ** gen):
case a ** b ** c =>
m.combine(a, m.combine(b, c)) == m.combine(m.combine(a, b), c)
.tag("associativity")
val identity = Prop
.forAll(gen): a =>
m.combine(a, m.empty) == a && m.combine(m.empty, a) == a
.tag("identity")
associativity && identity
它接受任意 Monoid[A] 与对应的 Gen[A],随机检验两条定律。productMonoid 之所以“免费”满足定律,正如上文所说,是因为它把定律验证逐分量分解到了两个已成立的幺半群上。
五、积幺半群的实战应用:从 bag 到嵌套组合
练习 16 的价值不仅在于自身,更在于它是本章“幺半群组合”路线的基石,后续多个练习直接建立在其思想之上。
5.1 与 mapMergeMonoid 的嵌套组合(练习 18)
18.answer.md 中的 mapMergeMonoid 是本章组合技巧的集大成者:
given mapMergeMonoidK, V: Monoid[Map[K, V]] with
def combine(a: Map[K, V], b: Map[K, V]) =
(a.keySet ++ b.keySet).foldLeft(empty): (acc,k) =>
acc.updated(k, mv.combine(a.getOrElse(k, mv.empty),
b.getOrElse(k, mv.empty)))
val empty = Map()
它与 productMonoid 共享同一套“用分量幺半群驱动整体”的组合思想:合并两个 Map 时,键的并集逐键调用值上的 mv.combine。MonoidSuite 中的 mapMergeMonoid 测试 展示了嵌套两层 mapMergeMonoid 的效果:
val M = mapMergeMonoid[String, Map[String, Int]]
val m1 = Map("o1" -> Map("i1" -> 1, "i2" -> 2))
val m2 = Map("o1" -> Map("i2" -> 3))
val m3 = M.combine(m1, m2)
assertEquals(m3, Map("o1" -> Map("i1" -> 1, "i2" -> 5)))
5.2 bag:用组合幺半群统计词频
bag 函数(answers/monoids/Monoid.scala)把 mapMergeMonoid 与 intAddition 组合,将每个元素映射为 Map(a -> 1) 后折叠,从而统计每个元素出现次数:
def bagA: Map[A, Int] =
import Foldable.given
as.foldMap(a => Map(a -> 1))
MonoidSuite 中 bag 测试 验证了空序列、重复元素、混合元素等情形,例如 bag(IndexedSeq("a", "rose", "is", "a", "rose")) == Map("a" -> 2, "rose" -> 2, "is" -> 1)。
5.3 functionMonoid:同样利用上下文参数(练习 17)
17.answer.md 的 functionMonoid 与 productMonoid 结构同构,只是把“元组分量”换成了“函数的返回值”:
given functionMonoidA, B: Monoid[A => B] with
def combine(f: A => B, g: A => B) = a => mb.combine(f(a), g(a))
val empty: A => B = a => mb.empty
两者都验证了同一模式:只要“容器”(元组、函数、Map)的每个分量/返回值上存在幺半群,容器整体就能自动获得幺半群结构。这也是第 10 章之后(第 11、12 章 Applicative/Monad)把幺半群“提升”进 Par 等上下文的前置铺垫——par、parFoldMap 正是这种思想的延续。
六、运行与验证
要在本地验证本章所有答案(包括 productMonoid),可参照 README.md 的构建说明,使用 Scala CLI:
# 编译全部练习与答案
scala-cli compile .
# 运行 monoids 相关的全部单元测试
scala-cli test . -- 'fpinscala.exercises.monoids.*'
其中 MonoidSuite 会随机生成大量元组样本对 productMonoid[String, Int] 执行结合律与单位元断言。运行全部测试前请注意:仓库刻意保留了未完成的练习桩,未完成的练习会导致对应测试失败,随着逐个完成练习测试会逐步转绿——这是该仓库设计的学习闭环。
七、小结
练习 16 的 productMonoid 用极简的代码传达了本章最核心的抽象能力:
- 幺半群可以组合:给定任意两个
Monoid,其笛卡尔积自动构成新的Monoid; - Scala 3 的 given/using 让组合自动化:
productMonoid作为 given 实例可被编译器隐式解析,并能与其他 given 实例无限嵌套; - 定律可以结构化验证:积幺半群的结合律与单位元由分量幺半群逐分量保证,既有单元测试佐证,也可用
monoidLaws做性质检验。
这一模式将在 mapMergeMonoid、functionMonoid、bag 以及后续章节的 Foldable、Par 提升中反复出现,是理解函数式组合设计的重要一环。相关完整实现可继续阅读 answers/monoids/Monoid.scala、answers/monoids/Foldable.scala 与测试 MonoidSuite.scala。