fold、reduce 与 sum

主线位置：主线 2 的结尾。sum 的消费者在每个叶子上顺序累加出一个部分和，回溯时由 Reducer 两两相加。fold、reduce 是同一个结构，只是把「怎么累加」「怎么合并」交给用户；它们的行为（identity 调多少次、结果是否确定）完全由 切分树 的形状决定。

flowchart TB
  root["reduce(identity, op)"] --> l["左半：叶子 A、B …"]
  root --> r["右半：叶子 C …"]
  l --> fa["叶子 A：acc = identity()，逐个 op(acc, x)"]
  l --> fb["叶子 B：acc = identity()，逐个 op(acc, x)"]
  r --> fc["叶子 C：acc = identity()，逐个 op(acc, x)"]
  fa --> m1["op(A, B)"]
  fb --> m1
  m1 --> m2["op(op(A, B), C)：根上的结果"]
  fc --> m2

fold：不是归约，是「每片一个」

fold(identity, fold_op) 返回的仍是一个并行迭代器 Fold<I, ID, F>，元素类型是累加值。FoldConsumer::into_folder 在每个叶子上调一次 identity()，FoldFolder::consume 做 fold_op(acc, item)；叶子 complete() 时把最终的 acc 作为一个元素交给下游消费者。

所以 fold 之后的迭代器有多少个元素，等于切分树有多少个叶子。E2 正是用 fold(|| (), |_, _| ()).count() 数叶子，并用自写 Producer 的计数核对过两者恒等。fold 的文档建议「先 fold 再 reduce / sum」：每片先在本地累加，下游只合并「叶子数」个值。典型用法是每片一个 Vec 或 HashMap，最后合并，避免每个元素都去碰共享结构。

fold 没有 opt_len，是 unindexed 的：叶子数不确定，输出个数就不确定。

fold_with(init, fold_op) 用一个值代替 identity 闭包，要求 init: Clone：消费者每次 split_at 都 clone 一份（fold.rs:243-248）。fold_chunks(n, identity, op)（indexed）则不看切分树，按固定的 n 个元素一组 fold，输出个数确定为 ⌈len / n⌉。

reduce：identity 调用次数 = 叶子数

reduce(identity, op) 的消费者是 Copy 的，split_at 返回三份自己；into_folder 调一次 identity()；ReduceFolder::consume_iter 是 iter.into_iter().fold(self.item, self.reduce_op)；Reducer::reduce 是 op(left, right)。

这带来文档里那两条要求：

• op 要满足结合律。树的形状每次不同，((a ⊕ b) ⊕ c) ⊕ d 和 (a ⊕ b) ⊕ (c ⊕ d) 都可能出现。左右顺序是保住的（left 永远是下标靠前的一半），所以不需要交换律：字符串拼接这种不满足交换律的 op 也能得到正确顺序。
• identity() 可能被调用很多次，次数等于叶子数（加上被 full() 提前截断的分支），而叶子数受窃取影响，从几十到几千不等（E2）。identity 必须真的是单位元，reduce(|| 1, |a, b| a + b) 会得到一个随调度变化的错误结果。

reduce_with(op) 不要 identity，内部用 Option 包一层：fold 时 None 遇到第一个元素就变成 Some，合并时两边都有才调 op（mod.rs:1017-1035）。空迭代器返回 None。

try_fold / try_reduce 用 Try（Result、Option、ControlFlow）表示可能失败的累加。try_fold 的 folder 遇到 Break 就让自己这个叶子的 full() 为真（try_fold.rs:154-158），其他叶子不知道；try_reduce 才有一个共享的 AtomicBool，Break 时置位，所有分支的 full() 都会读到（try_reduce.rs:113）。try_for_each(op) 就是 self.map(op).try_reduce(<()>::default, ok)，所以一个 Err 能让其他线程尽快停下。

sum：Sum trait 两两相加

sum.rs 不要求 S: Add，而是借 std 的 Sum trait：

fn add<T: Sum>(left: T, right: T) -> T {
    [left, right].into_iter().sum()
}

• identity 是 iter::empty::<T>().sum()（sum.rs:45-49），对数字就是 0。
• 叶子上 SumFolder::consume_iter 是 add(self.sum, iter.into_iter().sum())：整段用 std 的 Iterator::sum，编译器可以向量化。
• 合并时 add(left, right)，即 [left, right].into_iter().sum()。

product 是同一个形状，用 Product。S: Sum<Item> + Sum<S> 这个约束允许 Item 和 S 不同（比如对 &u64 求和得到 u64）。

浮点求和不确定

叶子内部是顺序加，叶子之间按树的形状两两加。浮点加法不满足结合律，树的形状一变，舍入就变。而树的形状由窃取决定（E2），每次运行不同。

exp-rayon/collect-paths/ 的 E8 第二部分：10⁶ 个 [0, 1) 的 f32（固定种子的 xorshift），各种方式重复 100 次，统计不同结果的个数：

• 12 线程下 100 次得到 4–5 个不同的 f32，相差到 0.1 量级。
• 1 线程是反向验证：没有窃取，树形确定，结果恒定。但它和顺序版也不相等（499846.13 对 499845.13）：1 线程池内的树是 2 片，两个部分和相加的舍入不同于一路加到底。所以「确定」不等于「等于顺序结果」。
• 用 with_min_len(len) 把树压成一个叶子，就是顺序求和，逐位相同（0.0 + s == s）。
• 这组数据换成 f64 累加后 100 次只有 1 个结果，只说明误差被 f64 的精度吸收了，不说明 f64 求和在一般情况下是确定的；结合律问题对 f64 同样存在。

需要可复现的浮点结果，要么固定树形（with_min_len 让每片足够大且片数确定，或者 fold_chunks 按固定大小分组后再顺序合并），要么在更高精度里累加，要么用补偿求和（Kahan）在每片内部减小误差（只是减小，仍不保证逐位一致）。

小结

• fold 每个叶子产出一个元素，元素个数 = 叶子数，所以它也是数叶子的工具；fold_with 每次切分 clone 一份初值。
• reduce 的 identity 每个叶子调一次，次数随窃取变化，必须是真正的单位元；op 要结合律，不需要交换律（左右顺序保留）。
• try_fold 的短路只作用于本叶子，try_reduce / try_for_each 用共享 AtomicBool 让所有线程尽快停。
• sum 借 Sum trait：叶子内用 std 的 sum，合并用 [left, right].into_iter().sum()。
• f32 并行求和随切分树变化（E8：12 线程 100 次 4–5 个结果，1 线程恒定但不等于顺序结果，单叶子与顺序逐位相同）。