一批输入产生了多个 Option，调用者要哪一种结果

逐项解析一批输入时，map 很容易得到 List[Option[Int]]。它保留每个位置的成功或缺失，但没有回答整批输入的成功条件。调用者可能希望任意一项失败就拒绝整批，也可能希望保留所有错误，还可能只需要筛出成功项。这些需求不能用同一个“展平”含糊处理。

本章先选择第一种契约：全部成功时返回原顺序的结果列表，出现缺失时返回 None。类型从 List[Option[A]] 变为 Option[List[A]]。这叫 sequence；如果输入还是 List[A]，需要先逐项应用 A => Option[B]，再组织整体结果，就对应 traverse。

前置是 Writer 与可组合日志，也需要理解 Applicative 的独立组合。已有 Scala 错误短路与错误累积区分了依赖检查与独立检查。本章保留那个边界，增加集合层面的类型转换和真实调用轨迹，不把旧文的领域校验模型重新写成另一个版本。

三个相似表达式有三个不同契约

对 List(Some(1), None, Some(2)) 使用集合 flatten，结果是 List(1, 2)。缺失位置被删除，输出长度缩短。它适合明确允许忽略缺失的场景，但不能表达整批数据都有效。实验保留这个否定断言，防止重构时把 sequence 换成看起来更短的 flatten。

sequence 的结果则是 None。它不返回部分成功列表，因为这个类型的成功分支承诺整批成功。如果业务还要知道哪一项失败，Option 本身就不够，需要 Either、Validated 或自定义错误类型；不能从 None 中恢复已经没有保存的索引和原因。

普通 map 的结果仍是 List[Option[Int]]，保留了三个位置各自的状态，但聚合判断还没发生。它并不比 sequence 低级，也不是未完成的代码。若页面要逐行展示导入状态，这种结构可能正合适。先决定调用者需要的是逐项状态、整批成功还是所有错误，再选择组合方式。

这三者的区别可以直接从类型阅读：外层 List 表示多个位置，外层 Option 表示整体可能缺失。类型层次不是装饰。把两层换位，意味着把“每一项是否有值”汇总成“整个结构是否有值”，必须规定如何处理任意一个 None。

从空列表开始推导 sequence

空列表没有失败项，因此应返回 Some(Nil)，而不是 None。这个选择很重要：空输入与解析失败具有不同含义。若业务规定不允许空批次，应在额外的业务验证中表达，而不是改变通用 sequence 的单位行为。

实验的简单实现如下：

def sequence[A](xs: List[Option[A]]): Option[List[A]] =
  xs.foldRight(Option(List.empty[A])) { (x, acc) =>
    x.flatMap(a => acc.map(a :: _))
  }

foldRight 的初始累积值类型是 Option[List[A]]。每次拿到 x: Option[A] 和已经组合好的 acc: Option[List[A]]。x 为 Some 时，取得 a；acc 也为 Some 时，把 a 放到列表头部。两者只要一个是 None，这一步就是 None。这里两个 Option 的成功值并不决定对方的计算方式，只是在成功时组装列表。

以 Some 二、Some 一为例，先有 Some 空列表，再形成 Some 单元素一，最后形成 Some 二一。结果顺序仍与输入一致。若把 a :: _ 错写成尾部追加，并保持这个折叠方向，就会倒序；若将空列表的初值写成 None，则任意输入都会失败。实验同时检查顺序、缺失和空输入，避免只用一个成功元素掩盖错误。

这个实现接收的是已经构造好的 Option 列表。它不能取消构造列表时发生的动作。即便内部遇到 None 后不再调用某个 map 回调，之前为所有元素调用解析函数的事实也不会改变。这一点在后面的调用计数中可以直接看到。

traverse 把逐项函数纳入组合过程

一个专门针对 Option 的教学实现可以把后续递归放进成功回调：

def shortTraverse[A, B](xs: List[A])
    (f: A => Option[B]): Option[List[B]] = xs match
  case Nil => Some(Nil)
  case h :: t =>
    f(h).flatMap(b => shortTraverse(t)(f).map(b :: _))

当前 f 返回 None 时，flatMap 不调用回调，因此后面的递归也不会发生。f 返回 Some 时才继续处理尾部，最后按原顺序组装列表。这段代码有利于观察控制流，但直接递归版本不应被当作长列表上的栈安全实现；本章没有为它增加 trampoline 或尾递归转换。

这个签名也显示了遍历与依赖链的区别。每一项使用同一个 A => Option[B]，当前项要检查什么由原输入 A 决定，不由前一个成功结果 B 决定。失败可以使后续求值停止，但“可能停止”不等于“下一项的函数依赖上一个结果”。这种独立结构正是通用 Traverse 可以只要求 Applicative 的原因。

Cats 的通用 traverse 将结构 T 中的每一项变成 F 中的结果，然后得到 F[T[B]]；sequence 是函数取 identity 时的对应操作。这里需要的能力是 F 的 Applicative，而不是一律要求 Monad。Cats Traverse

同样得到 None，调用轨迹却不同

实验输入是 List(1, 0, -1, 2)。解析函数对正数返回十倍值，对其他输入返回 None，并把每次收到的整数追加到 events。这个可变记录仅用于观测调用次数，不属于纯解析函数的业务实现；不能拿它作为纯函数等式无条件成立的前提。

手写 shortTraverse 返回 None，events 为一、零。第一个元素成功，第二个失败，后两个没有调用。先执行 xs.map(parse) 再执行 sequence 也返回 None，但 events 是完整输入一、零、负一、二，因为严格 List.map 已经调用全部 parse，sequence 只能处理它拿到的现成结果。

实验还直接运行 Cats 2.12.0 的 xs.traverse(parse)。在本次 List 与 Option 的组合下，events 同样是一、零。这个结论来自真实版本和实例的运行断言，不被推广为“任何 Traverse 都短路”或“任何 F 都懒求值”。换成另一个效果类型、另一个实例或预先启动的计算，需要重新检查相应的求值行为。

表达式	整体结果	本实验的 parse 调用输入
手写 shortTraverse	None	1、0
严格 map 后 sequence	None	1、0、-1、2
Cats List traverse Option	None	1、0

在纯函数层面，常用 traverse(f) 与 sequence(map(f)) 描述二者的关系；加入可观察副作用后，必须另外审查求值策略。只断言返回 None 会掩盖额外调用。对于数据库写入、发信等动作，额外调用不是性能小问题，而可能是已经发生的业务变化。本文没有执行这些外部动作，只用内存事件轨迹隔离这个差别。

也不要将“未调用后续回调”写成“取消了后续任务”。实验没有创建异步任务，更没有取消协议。若某个任务在进入 traverse 之前已经启动，后来不读取它的结果，并不意味着它停止运行。执行策略属于具体效果类型和运行机制，不能由 traverse 这个名字推出。

累积所有错误需要另一个组合规则

如果导入页面希望一次显示所有非法行，就不能在零处停止。实验把逐项结果改为 ValidatedNel[String, Int]：合法正数产生十倍值，零与负数产生带输入值的错误。仍然使用同一个 List.traverse，但由 Validated 的 Applicative 负责错误合并。

import cats.data.ValidatedNel
import cats.syntax.all.*

def validate(n: Int): ValidatedNel[String, Int] =
  if n > 0 then (n * 10).validNel
  else s"invalid:$n".invalidNel

val result = List(1, 0, -1, 2).traverse(validate)
assert(result.swap.toOption.get.toList ==
  List("invalid:0", "invalid:-1"))

完整实验还记录 validate 的调用输入，断言四项全部被检查，错误保持零、负一的顺序。NonEmptyList 表示失败时至少存在一条错误；不是在失败分支里放一个可能为空的错误列表，然后让调用者猜测空列表是什么意思。

空输入仍然成功，结果是 Valid 空列表。全部合法输入二、一得到 Some 二十、十的 Option 对照，确认成功路径没有因为错误处理抽象而改变顺序。成功与失败、非空与空输入都属于契约，不能只验证有两条错误的展示效果。

累积校验不意味着可以忽略数据依赖。如果第二步必须用第一步成功解析出来的日期来检查范围，第一步失败后就没有这个日期，无法无条件执行第二步。可以先累积彼此独立的字段解析错误，全部成功后再执行依赖这些字段的跨字段检查；这比声称“所有校验都能并行累积”更符合实际类型关系。

为什么不直接给 Validated 加普通 flatMap

Monad 风格的 flatMap 在失败时没有 A，因而无法调用 A => F[B] 获得后续错误。若把它定义成常见的失败短路，按照 Monad 派生的独立组合也会短路，无法同时保留当前 Applicative 的累积行为。问题不是方法名称被禁止，而是期望的操作之间必须保持一致。Cats 的 Validated 文档用这类冲突解释了它与 Monad 的区别。Cats Validated

这也说明 Traverse 放在 Monad 学习段落里，并不意味着 Traverse 是 Monad 的一个子方法。它连接了“结构中的多个计算”与“计算中的一个结构”。当 F 是 Option，可以利用短路；当 F 是累积型 Validated，可以合并错误；这些行为取决于选定的 Applicative。

同样，traverse 也不等于并行执行。这里所有函数都在当前同步实验中求值，没有线程池、并发度或调度参数。并行版本还要定义结果顺序、失败处理、取消与资源限制。不能因为每个输入相互独立，就假设库已经启动多个线程，更不能据此估计吞吐量。

在服务边界上选择返回类型

批量查询可以有几种合理接口。返回 List[Either[E, A]] 时，每个位置保留自己的结果，调用者可以显示局部成功；返回 Either[E, List[A]] 时，整体只表达一个失败或全部成功；返回 ValidatedNel[E, List[A]] 时，整体失败可以保留多条错误。这些不是格式偏好，而是不同的信息承诺。

如果还需要关联原输入，错误中应保存索引或业务标识。本章用整数文本标识坏输入，重复输入时可能产生相同错误字符串；真实导入表格往往还要行号。不能在最后只对错误消息去重，否则两行同样的错误可能变成一条，页面无法逐行定位。

还有一种需要提前决定的策略：部分成功是否真的可以接受。若前两项已完成外部写入，第三项失败，返回整体 Left 并不会自动回滚前两项。Traverse 组织的是值和计算，不提供跨数据库事务协议。若业务要求全有或全无，要在效果执行层设计事务或补偿，并单独验证。

手算与修改练习

先写出 List[Option[Int]]、Option[List[Int]] 和 List[Int] 在本章中的含义，再手算空列表、全 Some、含 None 三组输入。解释为什么 sequence 的空输入应成功，为什么 flatten 的成功列表不代表原输入全部有效。回答时要指出被保留或丢弃的信息，不能只说“外层与内层交换”。

修改实验，输入改为字符串列表，并在错误中保存行号。用 toIntOption 区分解析失败，再检查正数约束；同一行的正数检查依赖解析结果，不应在解析失败后编造整数继续执行。不同的行仍然可以累积错误。断言两个非法行都被返回，同时单行不会产生基于不存在数值的第二条错误。

另一个修改是给现有 Option 解析函数加调用计数，比较直接 traverse 与先 map 后 sequence。保持两者返回值相同，再故意断言调用次数相同，观察哪个反例会使断言失败。把这个失败解释为严格求值位置的差别，而不是 Monad 定律失效；测试中的计数已经使函数不再纯粹。

实验与参考

执行 node examples/functional-programming/run.mjs 24。九组 PASS 覆盖 sequence 顺序与空值、三种调用轨迹、累积错误顺序、成功顺序、空批次和 flatten 的信息损失。实验固定 Scala 3.3.7、Cats 2.12.0；回调轨迹结论只针对源码中实际运行的组合。

完整 Scala 源码、真实运行证据与公共 runner 提供可复跑入口。证据包含命令、环境、退出码、源码哈希和断言输出，没有并发或事务测试结果。

官方阅读材料为 Cats Traverse 与 Cats Validated。本章对求值轨迹的比较来自附带实验，而不是从 API 名称推断。