用内函数幺半群（Endofunction Monoid）实现 foldRight 与 foldLeft：FP in Scala 第 10 章练习 6 深度解析

• 示例工程

导读

本文围绕 fpinscala 仓库中 answerkey/monoids/06.hint.md 这一练习提示展开，深入拆解《Functional Programming in Scala》第 10 章（monoids）练习 6 的核心思想：把传入foldRight的二元函数(A, B) => B柯里化为A => (B => B)，从而借用"内函数幺半群"（endofunction monoid，即B => B在函数复合下构成的幺半群）把任意列表折叠统一收纳进foldMap。读完本文，你将掌握从类型签名出发推导实现的完整思路、foldLeft作为对偶（dual）的构造方式，以及compose/andThen方向约定对最终代码形态的决定性影响，并能在仓库源码与测试用例中验证结论。

练习背景：Monoid、foldMap 与前置练习链

在进入练习 6 之前，仓库中的练习序列已经铺垫了三块基石，理解它们才能读懂 hint 的提示：

1. 练习 2——dual（对偶幺半群）：任何一个幺半群都可以通过翻转combine的入参顺序得到对偶幺半群，且empty不变。参考答案见 answerkey/monoids/02.answer.md：

def dualA: Monoid[A] = new: def combine(x: A, y: A) = m.combine(y, x) val empty = m.empty

2. 练习 3——endoMonoid（内函数幺半群）：对任意类型A，A => A在函数复合下构成幺半群，identity是单位元。参考答案见 answerkey/monoids/03.answer.md。
3. 练习 5——foldMap：把map和fold合并为一次遍历，通过幺半群完成归约。参考答案见 answerkey/monoids/05.answer.md：

def foldMapA, B(f: A => B): B = as.foldLeft(m.empty)((b, a) => m.combine(b, f(a)))

练习 6 的任务正是：只用foldMap（以及前面定义好的endoMonoid、dual）重新实现foldRight与foldLeft。对应的练习占位代码位于 src/main/scala/fpinscala/exercises/monoids/Monoid.scala，目前以???形式等待填充：

def foldMapA, B(f: A => B): B = ??? def foldRightA, B(acc: B)(f: (A, B) => B): B = ??? def foldLeftA, B(acc: B)(f: (B, A) => B): B = ???

核心洞察：把(A, B) => B柯里化为A => (B => B)

hint 的第一句话是整个练习的灵魂：

Notice that the type of the function that is passed tofoldRightis(A, B) => B, which can be curried toA => (B => B).

foldRight的折叠函数类型是(A, B) => B——它同时接受"列表元素"和"累加器"。对它做柯里化（currying）后得到：

f.curried: A => (B => B)

这个类型签名极具暗示性：对每个元素a: A，f.curried(a)就是一个B => B的内函数。而恰好在练习 3 中我们已经知道，B => B对任意B都构成幺半群（endoMonoid）。

于是思路立刻清晰起来：

1. 用foldMap把列表as中的每个元素a映射成内函数f.curried(a)；
2. 用endoMonoid把这些内函数"复合"成一个总函数；
3. 最后把这个总函数作用到初始累加器acc上。

整个过程把"折叠"这个动作彻底抽象成了"复合函数"这个纯代数概念——这正是幺半群抽象能力的体现：foldMap 一次遍历即可完成映射与归约。

为什么B => B是一个幺半群

要确认上述方案可行，需要验证B => B确实满足幺半群的两条定律：

• 单位元（identity）：identity: B => B，即x => x。f compose identity == f、identity compose f == f对任意f成立。
• 结合律（associativity）：函数复合天然满足结合律，(f compose g) compose h == f compose (g compose h)。

需要注意的是，compose与andThen只是同一件事的两种书写方向：

f andThen g == g compose f

仓库的完整实现 src/main/scala/fpinscala/answers/monoids/Monoid.scala 选择了andThen方向，并注释说明这里存在方向选择：

// There is a choice of implementation here as well. // Do we implement it as `f compose g` or `f andThen g`? We have to pick one. def endoMonoid[A]: Monoid[A => A] = new: def combine(f: A => A, g: A => A) = f andThen g val empty = identity

方向约定（compose还是andThen）会直接影响后续foldRight/foldLeft使用endoMonoid还是dual(endoMonoid)，这是本文后续要重点辨析的细节。

用 foldMap + endoMonoid 实现 foldRight

先做类型层面的推演。设endoMonoid[B]: Monoid[B => B]，则：

foldMap(as, endoMonoid[B])(f.curried): B => B

再作用到acc上，得到B，恰好就是foldRight的返回类型。参考答案（answerkey/monoids/06.answer.md）给出的核心形式是：

def foldRightA, B(acc: B)(f: (A, B) => B): B = foldMap(as, endoMonoid)(f.curried)(acc)

下面用具体例子验证折叠顺序。取as = List(1, 2)、acc = "0"、f = (a, b) => a.toString + b，标准foldRight的结果应为"120"（即f(1, f(2, "0"))）。

• f.curried(1) = b => "1" + b，f.curried(2) = b => "2" + b；
• 若endoMonoid以f compose g定义（combine(f, g) = f compose g），foldMap从左向右累积复合，得到(b => "1" + b) compose (b => "2" + b)，作用到"0"上得到"1" + ("2" + "0") = "120"，正确；
• 若endoMonoid以f andThen g定义，foldMap累积出的总函数作用到"0"上会得到"210"，顺序颠倒——此时就必须改用dual(endoMonoid)。

这正对应仓库完整实现 src/main/scala/fpinscala/answers/monoids/Monoid.scala 中的写法与注释：

// The function type `(A, B) => B`, when curried, is `A => (B => B)`. // And `B => B` is a monoid for any `B` (via function composition). // We have to flip the order of params to the endo monoid since we // chose to define it as `f andThen g` instead of `f compose g`. def foldRightA, B(acc: B)(f: (A, B) => B): B = foldMap(as, dual(endoMonoid))(f.curried)(acc)

关于方向的两种约定（务必辨析）

由于endoMonoid本身是练习 3 的待实现函数，方向由实现者决定，因此存在两组等价但形态相反的写法：

hint 的原话"use the endofunction monoidB => Bto implementfoldRight。The implementation offoldLeftis then just the dual"对应的是第一行（compose方向）。本仓库在练习 3 解答与完整实现中选择andThen方向，因此在第二行——方向翻转通过dual来补偿，二者殊途同归。写作时请务必先确定自己endoMonoid的方向，再决定是否套用dual，否则折叠顺序会颠倒。

foldLeft 是 foldRight 的对偶：翻转参数 + 翻转幺半群

hint 的第二句话点明foldLeft的构造法：

The implementation offoldLeftis then just the dual.

foldLeft的折叠函数类型是(B, A) => B——累加器在左、元素在右，与foldRight恰好相反。因此需要做两处翻转：

1. 翻转函数参数：把f: (B, A) => B改写成a => b => f(b, a)，得到A => (B => B)；
2. 翻转幺半群方向：因为foldLeft从左往右累积，而foldMap内部也是从左往右用combine累积，需要用dual把组合方向倒转，使内函数复合后作用顺序符合"左折叠"语义。

参考答案（answerkey/monoids/06.answer.md）在compose约定下的写法：

// Folding to the left is the same except we flip the arguments to // the function `f` to put the `B` on the correct side. // Then we have to also "flip" the monoid so that it operates from left to right. def foldLeftA, B(acc: B)(f: (B, A) => B): B = foldMap(as, dual(endoMonoid))(a => b => f(b, a))(acc)

本仓库在andThen约定下的完整实现（src/main/scala/fpinscala/answers/monoids/Monoid.scala）则是不加dual的版本：

def foldLeftA, B(acc: B)(f: (B, A) => B): B = foldMap(as, endoMonoid)(a => b => f(b, a))(acc)

用非对称函数验证顺序：取as = List(1, 2)、acc = "0"、f = (b, a) => a.toString + b（注意这里是foldLeft的签名(B, A) => B），标准foldLeft结果为"210"（即f(f("0", 1), 2)）。foldMap累积出的总函数作用到"0"上恰好得到"210"，说明顺序正确。

补充一点：foldMap本身在 Monoid.scala 中是用标准库List.foldLeft实现的，因此"用foldMap实现foldLeft"并不构成循环依赖——foldMap是地基，我们自定义的foldRight/foldLeft都建在它之上。

效率提示：为什么"不要担心不够高效"

hint 最后特意安抚读者：

Don't worry if these implementations are not very efficient.

从实现结构看，这种写法确实比直接折叠低效，原因可以归纳为三点（属于对代码结构的推断，而非性能基准数据）：

1. 为每个元素构造一个闭包：f.curried(a)对列表的每个元素都会生成一个新的B => B函数对象；
2. 多一层函数复合：foldMap用combine逐步复合这些函数，最终得到的是一个"函数的函数"；
3. 最终一次调用才真正折叠：所有计算都推迟到把总函数作用到acc的那一刻才发生，中间经历了整条函数调用链。

因此这种实现的主要价值在于展示幺半群与foldMap的抽象威力、加深对"折叠 = 复合 + 应用"的理解，而非追求性能。工程实践中直接用标准库或尾递归实现折叠更合适。

仓库源码：answers 完整实现与 Foldable 中的复用

完整答案位于 src/main/scala/fpinscala/answers/monoids/Monoid.scala，四个核心函数一气呵成：

def foldMapA, B(f: A => B): B = as.foldLeft(m.empty)((b, a) => m.combine(b, f(a))) def foldRightA, B(acc: B)(f: (A, B) => B): B = foldMap(as, dual(endoMonoid))(f.curried)(acc) def foldLeftA, B(acc: B)(f: (B, A) => B): B = foldMap(as, endoMonoid)(a => b => f(b, a))(acc)

更值得注意的是，这套"内函数幺半群 + 对偶"的技巧在仓库中被提升到了抽象类型层面：src/main/scala/fpinscala/answers/monoids/Foldable.scala 的Foldable[F[_]]trait 以扩展方法的形式，为任意可折叠容器统一提供foldRight、foldLeft、foldMap、combineAll：

trait Foldable[F[_]]: import Monoid.{endoMonoid, dual} extension A def foldRightB(f: (A, B) => B): B = as.foldMap(f.curried)(using dual(endoMonoid[B]))(acc) def foldLeftB(f: (B, A) => B): B = as.foldMap(a => b => f(b, a))(using endoMonoid[B])(acc) def foldMapB(using mb: Monoid[B]): B = as.foldRight(mb.empty)((a, b) => mb.combine(f(a), b))

这里foldMap与foldRight互为表里：Foldable用foldRight定义foldMap，而Monoid对象用foldMap定义foldRight——两者在List、IndexedSeq、LazyList、Tree、Option等具体given实例中通过覆写各取所长（例如Foldable[IndexedSeq]的foldMap直接委托给平衡递归的Monoid.foldMapV）。这正是练习 6 的思想被"抽象化"后的形态：只要一个类型拥有幺半群化的折叠能力，foldRight/foldLeft就能免费获得。

用测试验证实现

仓库为 monoids 章节准备了完整的属性测试。练习 6 的相关断言在 src/test/scala/fpinscala/exercises/monoids/MonoidSuite.scala 中：

test("Monoid.foldMap")(genBooleanList): list => assertEquals(foldMap(list, intAddition)(trueCounter), trueCounter(list)) test("Monoid.foldRight")(genBooleanList): list => assertEquals(foldRight(list)(0)((b, acc) => trueCounter(b) + acc), trueCounter(list)) test("Monoid.foldLeft")(genBooleanList): list => assertEquals(foldLeft(list)(0)((acc, b) => trueCounter(b) + acc), trueCounter(list))

其中trueCounter(list) = list.count(identity)，即统计布尔列表中true的个数。测试以随机生成的布尔列表为输入，把foldRight/foldLeft的结果与直接计数比对。由于加法交换律的作用，该测试对"左右折叠顺序"不敏感——所以即便方向搞反也可能通过，这正是建议读者自行用非对称函数（如字符串拼接或减法）做交叉验证的原因。

此外，FoldableSuite.scala 还会对List、IndexedSeq、LazyList、Tree、Option五种容器的foldRight/foldLeft/foldMap/combineAll做一致性校验，可作为抽象层实现正确性的佐证。

按仓库 README.md 的说明，可以用 Scala CLI 运行 monoids 包的测试：

scala-cli test . -- 'fpinscala.exercises.monoids.*'

或者进入 REPL 手工实验：

scala-cli console .

需要提醒的是：练习文件中的foldMap、foldRight、foldLeft目前都是???占位，直接运行测试会失败；按本文方案填充实现后，相应测试即会转绿——这也与 README 中"随着你解出练习，测试开始通过"的说明一致。

小结

练习 6 的核心价值不在于"用另一种方式写折叠"，而在于一次类型驱动的抽象跃迁：

• 观察类型：(A, B) => B柯里化后是A => (B => B)，暴露出"每个元素对应一个内函数"的结构；
• 复用幺半群：B => B在函数复合下天然是幺半群（identity为单位元，复合满足结合律），因此foldMap+endoMonoid即可完成折叠；
• 对偶补全：foldLeft只需翻转函数参数顺序并用dual翻转幺半群方向；
• 方向辨析：compose与andThen两种约定导致endoMonoid/dual(endoMonoid)的选用互换，本仓库源码以andThen方向给出了自洽且带注释的实现；
• 效率取舍：该写法以函数对象与复合为代价换取概念上的统一，适合教学演示而非性能敏感场景。

配合 answerkey/monoids/06.hint.md 的提示、answerkey/monoids/06.answer.md 的参考答案、answers 完整实现 与 测试套件，读者可以从"提示 → 推导 → 实现 → 验证"四个环节完整消化这一经典练习，并顺带理解Foldable抽象层的设计动机。

• 示例工程