企业官网建设流程全解析

• 示例工程

导读

本篇围绕《Functional Programming in Scala》配套仓库 fpinscala 中第 3 章（datastructures）练习 8 的官方答案展开，深入剖析foldRight的本质：它本质上是用一个初值z替换列表的Nil构造器、用一个二元函数f替换Cons构造器。掌握这一视角后，你不仅能轻松解释"为什么foldRight(list, Nil)(Cons)会原样返回输入列表"，还能一通百通地理解append、concat、map、filter等一批列表函数为何都能建立在foldRight之上，并清楚其严格求值带来的栈安全局限。读完本文，你将具备从"折叠"这一统一抽象重新审视列表操作的能力，并能在仓库源码与测试中验证每一个结论。

练习背景：这一题在问什么

在 fpinscala 仓库中，第 3 章的数据结构练习位于 src/main/scala/fpinscala/exercises/datastructures/List.scala。本章让读者用递归和模式匹配从零实现一个函数式链表：

enum List[+A]: case Nil case Cons(head: A, tail: List[A])

练习 8 要求基于已实现的foldRight完成一些列表函数。官方答案文件为 answerkey/datastructures/08.answer.md，它首先提出并解答了一个关键疑问：当用Nil作为初值、Cons作为合并函数去折叠一个列表时，会得到什么？

答案出人意料又顺理成章——我们得到的就是原来的列表。本篇将逐层拆解这背后的原理。

foldRight 的官方实现：先看它到底做了什么

要理解"为什么能还原原列表"，必须先看foldRight的真实实现。在完整解答模块 src/main/scala/fpinscala/answers/datastructures/List.scala 中：

def foldRightA, B => B): B = as match case Nil => z case Cons(x, xs) => f(x, foldRight(xs, z, f))

它通过模式匹配递归地处理列表：

• 遇到Nil（空列表）时，直接返回初值z；
• 遇到Cons(x, xs)时，把当前元素x与"对剩余部分xs递归折叠的结果"一起交给函数f。

注意这里的递归调用发生在f的第二个参数位置（f(x, foldRight(...))），因此foldRight会先一路递归到列表尾部，再从右向左合并——这正是"右折叠"名称的由来。练习 8 的提示文件 answerkey/datastructures/08.hint.md 也点明了第一步追踪结果：Cons(1, foldRight(Cons(2, Cons(3, Nil)), Nil:List[Int])(Cons(_,_)))。

核心洞察：折叠就是"替换构造器"

官方答案给出了一个非常深刻的视角（见 answerkey/datastructures/08.answer.md）：

一种理解foldRight"做了什么"的方式是：它把列表的Nil构造器替换为参数z，把Cons构造器替换为给定的函数f。

换句话说，列表Cons(1, Cons(2, Cons(3, Nil)))可以看作一棵由构造器搭成的树。foldRight并不"遍历"这棵树去做什么，而是对整棵树做一次结构替换：

• 树底部的Nil被换成z；
• 每一层Cons(head, tail)被换成f(head, 替换后的tail)。

因此，如果我们提供Nil作为z、Cons(_, _)作为f，那么每个构造器都被替换成了它自己——整棵树的结构纹丝不动，折叠的结果自然就是原列表。这种"把数据类型的所有构造器逐一映射为对应处理函数"的折叠，在函数式编程中被称为该数据类型的catamorphism（初始代数上的同态），foldRight正是列表这个代数数据类型上的 catamorphism。

逐步展开：逐行追踪还原过程

官方答案给出了完整的逐步展开（以下追踪与 answerkey/datastructures/08.answer.md 一致，仅补充了每步的说明）：

foldRight(Cons(1, Cons(2, Cons(3, Nil))), Nil:List[Int])(Cons(_,_))

第 1 步：最外层是Cons(1, ...)，按定义foldRight展开为f(1, foldRight(剩余部分))，即：

Cons(1, foldRight(Cons(2, Cons(3, Nil)), Nil:List[Int])(Cons(_,_)))

第 2 步：内层继续处理Cons(2, ...)：

Cons(1, Cons(2, foldRight(Cons(3, Nil), Nil:List[Int])(Cons(_,_))))

第 3 步：继续处理Cons(3, ...)：

Cons(1, Cons(2, Cons(3, foldRight(Nil, Nil:List[Int])(Cons(_,_)))))

第 4 步：触底！foldRight遇到Nil，按定义直接返回初值z = Nil：

Cons(1, Cons(2, Cons(3, Nil)))

四条展开式逐一展示了"构造器替换"的过程：Cons留在原地（被f = Cons替换后形态不变），只有最底层的Nil被替换为初值Nil。由于初值恰好也是Nil，替换前后完全一致。

这里有一个值得注意的细节：官方答案（以及 src/main/scala/fpinscala/answers/datastructures/List.scala 中的注释）使用的是柯里化写法foldRight(list, Nil)(Cons(_,_))，而本章实际实现是foldRight(as, z, f)的三参数形式；两者等价，Cons(_,_)则是(x, xs) => Cons(x, xs)的简洁写法。在 REPL 中可直接验证：

$ scala-cli console . scala> import fpinscala.answers.datastructures.List scala> List.foldRight(List(1,2,3), Nil: List[Int])(Cons(_, _))

空列表：构造器替换视角的极限情形

把上面的视角推广到空列表会得到一个漂亮的结论：foldRight(Nil, z)(f)不需要替换任何Cons，直接返回z。因此：

foldRight(Nil, Nil: List[Int])(Cons(_, _)) == Nil

空列表折叠空列表，结果仍是空列表。这与其他折叠操作保持一致——foldRight的初值z就是"空列表折叠出来的值"。

一通百通：基于 foldRight 构建的列表函数

理解了"替换构造器"的本质后，练习 8 中其余函数的实现就变得非常自然，它们全部建立在这一视角之上。

append：把第二个列表塞进第一个列表的 Nil 位置

append(l, r)的含义是"把l的Nil换成r"，这正是foldRight的本职工作（src/main/scala/fpinscala/answers/datastructures/List.scala）：

def appendViaFoldRightA: List[A] = foldRight(l, r, Cons(_,_))

对比还原列表的写法foldRight(l, Nil, Cons(_,_))：唯一的区别是把初值Nil换成了第二个列表r。这正是"替换构造器"的直接应用——l的底部Nil被替换为r，其余Cons原样保留。

concat：拼接列表的列表

把这一思想再推一层，concat(l: List[List[A]])就是把外层列表中每个元素（一个列表）的Nil都替换成"后续所有列表拼接的结果"（src/main/scala/fpinscala/answers/datastructures/List.scala）：

def concatA: List[A] = foldRight(l, Nil: List[A], append)

由于foldRight是右结合的，append的第一个参数（即外层列表的头部列表）长度固定不变，整个concat的时间复杂度与所有列表的总长度成线性关系。

map / filter / flatMap：统一用 foldRight 表达

练习 8 的后续部分展示了大量以foldRight为骨架的高阶函数：

def mapA, B: List[B] = foldRight(l, Nil: List[B], (h, t) => Cons(f(h), t)) def filterA: List[A] = foldRight(l, Nil: List[A], (h,t) => if f(h) then Cons(h,t) else t) def flatMapA, B: List[B] = concat(map(l, f))

用构造器替换的视角看：

• map：把每个Cons(h, t)替换为Cons(f(h), t)，即保持结构、只替换元素；
• filter：把Cons(h, t)替换为if f(h) then Cons(h,t) else t，即"符合条件的元素保留Cons，不符合的直接丢弃t"；
• flatMap：先map得到List[List[B]]，再concat拍平，本质仍是两层构造器替换。

这些实现都能在 src/main/scala/fpinscala/answers/datastructures/List.scala 中找到完整版本，并有对应的属性测试在 src/test/scala/fpinscala/exercises/datastructures/ListSuite.scala 中验证（例如map与 Scala 标准库List.map的结果逐一比对）。

局限一：严格求值下无法提前终止

"替换构造器"视角还能解释一个常见困惑：foldRight能否像短路求值那样提前返回？练习 7 的答案（answerkey/datastructures/07.answer.md）明确指出：不能。

原因是 Scala 默认是严格求值（strict evaluation）的。在f(x, foldRight(xs, z, f))中，调用f之前必须先求出第二个参数foldRight(xs, z, f)的值，而求这个值又必须先递归到列表末尾。也就是说，在调用f之前，整个列表已经被遍历完毕。要让折叠支持提前终止，需要非严格（惰性）求值——这正是本书第 5 章讨论 LazyList（惰性列表）时的主题。

局限二：严格的 foldRight 不是栈安全的

从逐步展开中不难发现：foldRight的每次递归都先压栈、等到触底后再逐层返回，因此递归深度等于列表长度。对长列表而言，这会耗尽调用栈（stack overflow）。练习 10 的foldLeft（answerkey/datastructures/10.answer.md）是尾递归的、栈安全，因此常见的补救手法是用foldLeft重新表达foldRight（见 src/main/scala/fpinscala/answers/datastructures/List.scala）：

def foldRightViaFoldLeftA, B => B): B = foldLeft(reverse(l), acc, (b, a) => f(a, b))

先reverse再foldLeft，让元素从右向左被处理，既保持了右折叠的结合顺序，又利用了foldLeft的尾递归特性。练习 13 的答案（answerkey/datastructures/13.answer.md）还给出了利用函数组合（把B实例化为B => B）实现foldRightViaFoldLeft_1与foldLeftViaFoldRight的"理论趣味"版本，并提醒这类实现同样不是栈安全的，仅用于加深对折叠顺序的理解。

视角推广：Tree.fold 也是"替换构造器"

这一视角并非列表独有。在本章随后的 Tree 练习中，官方解答 src/main/scala/fpinscala/answers/datastructures/Tree.scala 给出了Tree的fold：

def foldB => B): B = this match case Leaf(a) => f(a) case Branch(l, r) => g(l.fold(f, g), r.fold(f, g))

fold接收每个数据构造器对应的"处理器"：Leaf的值由f: A => B处理，Branch的两个子树结果由g: (B, B) => B合并。源码注释（src/main/scala/fpinscala/answers/datastructures/Tree.scala）明确指出它与foldRight的类比：t.fold(Leaf(_))(Branch(_,_)) == t——用构造器本身作为处理器折叠，得到的就是原树。这与列表的foldRight(list, Nil)(Cons)如出一辙：折叠是"构造器替换"的通用模式，适用于一切递归代数数据类型。

小结与验证路径

回顾本篇的核心结论：

1. foldRight(as, z, f)的本质是把列表的Nil替换为z、把每个Cons替换为f，即列表上的 catamorphism；
2. 因此foldRight(list, Nil: List[Int])(Cons(_,_))返回原列表，空列表折叠后仍是空列表；
3. 同一视角可直接推导出append、concat、map、filter、flatMap等函数的 foldRight 实现；
4. 严格求值使foldRight既无法提前终止、也不是栈安全的，需借助非严格求值或foldLeft变体解决；
5. 该模式可推广到Tree.fold等其他递归数据类型。

如果你想亲手验证以上所有结论，可在仓库根目录运行：

$ scala-cli test . -- 'fpinscala.exercises.datastructures.*'

运行针对 datastructures 包的属性测试；随着练习逐步完成，测试会依次通过（详见 README.md）。完整的练习骨架在 src/main/scala/fpinscala/exercises/datastructures/List.scala，官方答案与注释则在 src/main/scala/fpinscala/answers/datastructures/List.scala 与 answerkey/datastructures 目录中，可随时对照阅读。

• 示例工程