fpinscala 第 3 章练习 20 精解：用 map 与 concat 组合实现 List.flatMap

• 示例工程

本文聚焦于《Functional Programming in Scala》配套仓库 fpinscala 第 3 章（datastructures）练习 20 的官方提示（answerkey/datastructures/20.hint.md）与标准答案，系统讲解如何在不使用显式递归的前提下，用已经实现好的map与concat组合出flatMap，并进一步从源码与测试两个层面验证实现的正确性。读完本文，你将掌握flatMap的“先映射、再压平”本质、它与foldRight的等价关系，以及它在本书后续 Monad 章节中的核心地位。

练习背景：自建 List 与即将完成的工具箱

本章要求读者在fpinscala.exercises.datastructures包中逐步构建自己的不可变单链表。该数据类型在 src/main/scala/fpinscala/exercises/datastructures/List.scala 中定义为 Scala 3 枚举：

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

配套的List伴生对象中，练习 20 之前已经依次完成了tail、setHead、drop、dropWhile、init、length、foldLeft、reverse、appendViaFoldRight、concat（练习 15）、incrementEach（练习 16）、doubleToString（练习 17）、map（练习 18）、filter（练习 19）等函数。其中与本题直接相关的两个“现成零件”是：

• map：对每个元素应用函数f，结果类型为List[List[B]]（当f: A => List[B]时）；
• concat：把一个嵌套列表List[List[A]]压平为一层List[A]。

练习 20 的任务签名位于 exercises/List.scala 第 84 行：

def flatMapA,B: List[B] = ???

官方提示原文与解读

本练习的提示文件 answerkey/datastructures/20.hint.md 全文只有一句话：

You should be able to use a combination of existing functions.

（你应该可以用现有函数的组合来实现。）

这句话点明了本题的考查意图：组合复用而非重新发明轮子。提示刻意不指名具体函数，意在引导读者自己发现map与concat的“接力”关系——map负责把每个A展开成一段List[B]，concat负责把所有小段拼接成一条完整的List[B]。这正是flatMap在集合语义上的标准定义：先map再flatten。

标准答案与逐步推导

官方答案位于 answerkey/datastructures/20.answer.md：

def flatMapA,B: List[B] = concat(map(l, f))

答案的注释还补充道：这个函数也可以直接用foldRight实现。下面给出两种视角的推导。

推导一：从类型看组合

假设输入为List(1, 2, 3)，函数f = a => List(a, a)：

1. map(l, f)：对1、2、3分别调用f，得到List(List(1,1), List(2,2), List(3,3))，类型为List[List[Int]]；
2. concat(...)：利用 concat 的实现——foldRight(l, Nil: List[A], append)——把嵌套列表逐层append合并，得到List(1, 1, 2, 2, 3, 3)。

两个步骤各自职责单一，组合起来恰好满足flatMap的签名(List[A], A => List[B]) => List[B]。

推导二：直接基于 foldRight 的等价实现

回顾foldRight的定义（answers/List.scala 第 39-42 行）：

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

它的语义是“用z替换Nil、用f替换Cons”。把z设为Nil: List[B]，把f设为“先对当前元素调用f得到一段列表，再append到已折叠的尾部”，即可得到直接版本：

def flatMapViaFoldRightA,B: List[B] = foldRight(l, Nil: List[B], (h, t) => append(f(h), t))

两种写法在语义上完全等价：concat(map(l, f))展开后就是先逐元素map、再统一append压平，而foldRight版本把“展开 + 拼接”合并进一次右折叠中。concat本身也是通过foldRight定义在append之上的，因此二者本质上共享同一条递归骨架。

用标准库与测试用例验证正确性

仓库在 src/test/scala/fpinscala/exercises/datastructures/ListSuite.scala 中为flatMap提供了基于属性测试框架的用例：

test("List.flatMap")(genIntList): list => assertEquals( List.flatMap(list, a => List(a, a)), scalaListToList(listToScalaList(list).flatMap(a => SList(a, a))) )

该测试的做法是：把自定义List转成 Scala 标准库scala.List，调用标准库的flatMap作为参照实现，再转回自定义类型与练习实现比对。测试数据由Gen随机生成，能覆盖任意长度与取值范围的列表。这意味着只要实现与标准库flatMap的语义一致，测试即通过——这是验证“组合实现正确性”的最直接证据。

延伸一：用 flatMap 反推 filter（练习 21）

flatMap的价值在下一个练习中立刻得到体现。练习 21 要求基于flatMap重新实现filter，答案见 answerkey/datastructures/21.answer.md：

def filterViaFlatMapA: List[A] = flatMap(l, a => if f(a) then List(a) else Nil)

思路：对每个元素，若满足谓词则“展开”成单元素列表List(a)，否则“展开”成空列表Nil，最后由flatMap自动把结果压平。这展示了flatMap是一种比filter更基础的运算：它能表达“零个或多个结果”的语义，filter只是它的特例。对应的测试 ListSuite.scala 第 107-111 行 同样以标准库filter为参照进行比对。

延伸二：flatMap 在 Monad 章节中的位置

flatMap不仅是集合操作，更是函数式编程中 Monad 的“绑定”运算。在本书第 11 章，src/main/scala/fpinscala/answers/monads/Monad.scala 中为自定义List提供的Monad实例正是直接复用本章实现：

override def flatMapB = fa.flatMap(f)

也就是说，练习 20 写出的这个函数，会在后续章节成为List这个 Monad 实例的基石，并参与map、map2、sequence等所有 Monad 衍生运算的构建。从源码结构可以推断，本书的练习设计刻意让“集合工具函数”与“抽象代数结构”共用同一套命名与语义，帮助读者建立从具体到抽象的迁移能力。

复杂度与栈安全性讨论

从实现来看，concat(map(l, f))的时间复杂度约为O(n + 总输出长度)：map遍历输入列表一次（O(n)），concat通过右折叠对每个片段执行append。由于 concat 的实现 利用了foldRight的右结合性，append的第一个参数始终是当前已处理的短片段，因此整体呈线性，不会因累加导致平方级开销。

需要留意的是，本书目前版本的foldRight是严格求值的递归实现（answers/List.scala 第 39-42 行），因此无论是map、concat还是flatMap，对超长列表都存在栈溢出风险。答案文件在练习 18（map）的注释中明确给出了两种规避思路：一是用foldRightViaFoldLeft改写（map_1 实现），二是利用函数内部私有的ListBuffer做局部可变累积（map_2 实现），并强调只要可变状态不逃逸出函数边界，引用透明性依然成立。这些讨论同样适用于flatMap。

在本地运行与验证

仓库使用 Scala CLI 构建（详见 README.md），你可以这样验证本练习：

# 编译整个项目（包含练习与答案） scala-cli compile . # 进入 REPL 并导入自定义 List scala-cli console . scala> import fpinscala.exercises.datastructures.List # 运行 datastructures 包的全部单元测试 scala-cli test . -- 'fpinscala.exercises.datastructures.*'

注意 README 特别说明：初始状态下运行全部测试会存在失败，随着你逐步完成练习，测试会逐个转绿；flatMap的测试位于ListSuite中，完成练习 20 后即可通过。

小结

练习 20 的核心收获可以浓缩为三点：

1. 组合优于重写：flatMap = concat ∘ map，用一个签名互补的现有函数组合替代显式递归，代码更短、更不易出错；
2. foldRight 是万能骨架：concat、map、filter以及flatMap的等价实现都可以归结为一次右折叠，理解了foldRight就理解了本章一半以上的函数；
3. 语义与测试闭环：仓库提供的属性测试以标准库flatMap为参照，从行为层面锁定了实现的正确性，而 Monad 章节的复用则证明了该函数在更大抽象体系中的价值。

• 示例工程