common/monoid: make fold a balanced reduction - #1548

Reviewed at fcfe1345, baseline origin/main = 725129fe ("Remove unreachable throw in djs serializer's constSerialize (#1544)").

The core of this is right, and I checked the association-order question directly rather than taking the Monoid contract on faith. Three things need attention, one of them behavioural.

What I verified

Every Monoid instance in the repo, tested for associativity rather than assumed. Six instances reach fold: bigint.sum, bigint.product, number.sum, string.concat, and bit_vec's tryUnpackConcat for each of lsb/msb. (Three more reach repeat, which this PR does not touch: prime_field pow, secp mul, bit_vec.repeat.) 2000 random triples per instance:

• bigint.sum, bigint.product, string.concat — 0/2000 non-associative, identity law holds both sides.
• number.sum — 281/2000 non-associative, as expected for IEEE-754.

Old vs new fold swept over lengths 0–40 plus 63/64/65, 127/128/129, 255/256/257 (straddling the binary-counter merge points):

• bigint.sum, bigint.product, string.concat — identical at every length.
• number.sum — differs at 30 of the 50 lengths, first at n=5 (8044369.416131745 vs ...744).

Negative-controlled with the bracketing monoid: n=4 old (((ab)c)d) vs new ((ab)(cd)), n=8 old fully-left vs new (((ab)(cd))((ef)(gh))), so the comparison does detect regrouping.

On number.sum: neither answer is "correct" — the exact sum is representable by neither. The new grouping has the better error bound (O(log n·ε) vs O(n·ε)), so this is an improvement, not a regression, and it is disclosed. Not asking for a **BREAKING CHANGES:** prefix: on the repo's precedent that marks specifier/API breaks (#1520), not a last-ulp numerical shift (#1524 was representation-only and unprefixed). Flagging it only so the judgement is on the record.

bit_vec: 280 old-vs-new comparisons — tryListToVec and tryU8ListToVec, both bit orders, all the lengths above, plus an oversized element at every position for L=2..9, plus totals of exactly maxLength-1/maxLength/maxLength+1. 0 differences. The absorbing-null argument holds: lengths are additive and non-negative, so no partial combine overflows unless the total does, and the final combine always sees the full total.

Battery: npx tsc --noEmit 0 · npm run prepack 0 in both trees · npm test 2647 pass / 0 fail vs 2646 on main (+1 = the new balanced case; the bit_vec overflow case was extended in place) · link-check broken sets identical, 154 = 154, empty symmetric difference, and no stranded reference to the deleted todo/balanced-fold.md · public const surface: nothing added or removed, only fold's parameter name ({ identity, operation } → monoid), same type · type surface: _ListToVecOp/_ListToVecState removed, _Stack added — correctly _-prefixed, no §6.2 issue · @module survives into both emitted declarations, no elided/any.

§3.2 mutation testing of the new proofs, not just their names. monoid.proof.fold.balanced kills: never merging (stack.size !== size → always push) and reversing combine's run order. bit_vec.proof.tryListToVecOverflow kills dropping the maxLength cap. Correcting my own error: my first attempt at "swap the merge operands" appeared to survive, but the replacement had landed on the JSDoc at line 81 that quotes operation(stack.value)(value) rather than the code at line 89. Applied to line 89 it is killed ((ba) vs (ab)). The proof is sound; my mutation was not.

1. tryListToVec / tryU8ListToVec no longer terminate on an unbounded lazy list

List<T> includes Thunk<T> = () => List<T>, and tryFold exists precisely so a fold can bail out. Dropping it costs more than an extra walk. On an infinite lazy list whose prefix already overflows:

• main: returns null in 2 ms, pulling 0 elements past the overflow.
• this PR: still pulling at 200,000 elements past the overflow when I cut it off. It never terminates.

The PR describes this as "an already-doomed list is still walked to completion" and treats it as a bounded cost. For a finite list that is accurate. For a lazy unbounded one it is non-termination, which is a different statement — and maxLength is only 0x100000 (1 Mbit = 128 KiB), so overflow is an ordinary outcome, not an exotic one: any byte stream over 128 KiB through tryU8ListToVec reaches it. A try-prefixed function returning Nullable<Vec> is exactly what you would reach for when handed an untrusted or generated stream, which is the case that now hangs.

I do not think this sinks the design — reusing one generic fold is a good trade. But the JSDoc on tryUnpackConcat should say that unbounded lazy input no longer terminates, rather than implying the cost is just a completed walk.

2. The CHANGELOG names only common/monoid, but types/bit_vec changed observably

The entry covers fold alone. fjs/types/bit_vec/module.f.mjs is rewritten (−54/+46) and its public tryListToVec/tryU8ListToVec changed behaviour in the way above. §8.3 wants an entry for the code change, and the termination change in particular is the kind of thing a reader of the CHANGELOG needs. This is the same shape as #1540 and #1542, where the entry named one function and a second had moved too.

3. The CHANGELOG's complexity claim is wrong for two of the three cases it names

taking bigint.product and string/bit_vec concatenation from O(n²) to O(n log n)

Measured here, n=20,000, main vs this branch:

• bigint.product — claim holds, ~4x, and plausible against the code given V8's subquadratic multiplication.
• string.concat — not O(n²) to begin with: V8 builds ropes, so left-folded concatenation is already ~O(1) per step. This PR makes it measurably slower, not faster. The PR description says exactly this; the CHANGELOG says the opposite.
• bit_vec concatenation — was already O(n log n) on main. The deleted listToVecOp was a binary-counter accumulator and its own JSDoc said "O(n log n) total bigint shifting work instead of the O(n²) of a naive left fold". It is unchanged, not improved.

The honest entry is that bigint.product improves, bit_vec is refactored onto the shared combinator at equal cost, and string.concat pays a small price for uniformity.

Everything else checks out, and the balanced proof using a deliberately non-associative bracketing operation to pin the grouping is the right way to test this — a lawful monoid could not observe it. Happy to approve once the CHANGELOG is accurate and the non-termination is documented.

Re-reviewed at 8ece6666 (previously commented at fcfe1345). Baseline origin/main = 725129fe.

The delta since the last round is documentation only — the JSDoc on tryUnpackConcat, a new todo/listtovec-overflow-early-exit.md, and a rewritten CHANGELOG. Two of the three open items are genuinely closed; the third is now accurately described rather than fixed, and I think it still needs one change before merge.

Resolved: CHANGELOG now names types/bit_vec, and the characterisation checks out

The Unreleased section carries a separate types/bit_vec entry, and every claim in it holds when measured. Same shape as the fix applied to #1540 and #1542.

Resolved: the complexity claim now matches measurement

The old wording claimed string/bit_vec concatenation went from O(n²) to O(n log n), which was wrong on both. I re-measured rather than accepting the rewrite — main @ 725129fe vs this head, n = 20 000, best of 3 after a warm-up:

Three accurate statements where there were previously two wrong ones.

Still open: tryListToVec / tryU8ListToVec do not terminate on an unbounded lazy list

I re-ran the experiment at this head rather than taking the disclosure's word for it. An unbounded Thunk list of 32-bit vectors, so the prefix crosses maxLength (0x100000 bits = 128 KiB) after 32 768 elements:

• main 725129fe: msb.tryListToVec(inf) returns null after 32 769 pulls in 14 ms. Bounded, terminating.
• this head 8ece6666: still pulling at 54 731 606 elements after 15 s, at which point I aborted it. It is a tight synchronous loop — the process does not even service a setInterval. It never returns.

That is 1670× more elements than main pulls, and growing without bound. The documentation is now honest about this: the JSDoc says "keep pulling elements forever and never return", the CHANGELOG says "an unbounded lazy list past maxLength never returns", and the new todo/ file reproduces my earlier numbers and proposes the right fix (an absorbing element on Monoid so the shared fold can stop, rather than hand-rolling the walk back in bit_vec). I agree with that design — putting the early exit in the combinator is better than reverting bit_vec to its own accumulator.

But disclosure is not the same as a fix, and I do not think this one should ship deferred at P3:

• Termination → non-termination is a different category from a slowdown. Every other cost in this PR is a constant factor; this one is unbounded.
• It lands on exactly the API a caller reaches for when the input is untrusted. A try-prefixed function returning Nullable<Vec> advertises "hand me anything, I will tell you if it does not fit" — and maxLength is only 128 KiB, so overflow is an ordinary outcome, not an exotic one. The todo file makes both of these points itself.
• "Hand them a finite list" is not a precondition the type expresses: List<T> includes Thunk<T>, and nothing at the boundary distinguishes the finite case.

Two ways out, either fine by me:

1. Implement the absorbing proposal in this PR. It is small — an optional field on Monoid, one === absorbing check in push, and bit_vec sets it to null.
2. If it stays deferred, the CHANGELOG entry needs the **BREAKING CHANGES:** prefix (AGENTS.md §8.4). Published exports on both lsb and msb — tryListToVec, listToVec, tryU8ListToVec, u8ListToVec — change from returning to hanging on an input class they previously handled. This series has used the prefix for considerably less (fjs/ci/deno no longer exports coverageInclude). It is not the same case as number.sum's rounding drift, which I agree stays unprefixed on the #1520-vs-#1524 precedent: that is a value moving within its documented contract, not a call that stops returning.

Verified clean

• npx tsc --noEmit exit 0; npm run prepack exit 0 from a freshly cleaned tree (both passes).

• npm test: 2647 pass / 0 fail, against 2646 on 725129fe. The +1 is the new fold.balanced case.

• Public surface, both axes, after prepack in each tree: fold's signature goes from ({ identity, operation }: Monoid<T>) to (monoid: Monoid<T>) — same type, nothing widened to any. _ListToVecOp and _ListToVecState drop, _Stack<T> is added; all three are _-prefixed per §6.2, so no unprefixed additions. @module survives emit in both changed modules, no elided/any in the declarations.

• Broken-link sets identical to main, 154 entries either side — the todo/balanced-fold.md deletion strands nothing.

• §3.2, mutation-tested rather than read off the case names. Four mutations to module.f.mjs, each confirmed to have landed on code (not on a JSDoc line quoting the expression, which is how one appeared to survive last round), each run against the co-located proof in isolation:

  • swap the merge order in push → fold.order and fold.balanced both fail
  • never merge (stack.size !== size → true) → fold.balanced fails with (((ab)c)d)
  • swap the operand order in combine → fold.order and fold.balanced both fail
  • size * 2 → size → fold.balanced fails

  All four caught. The bracket monoid in fold.balanced is a good way to make grouping observable, and the comment explaining why a deliberately non-associative operation is legitimate there is exactly right.

• bit_vec's three-element overflow addition: dropping either null guard in tryUnpackConcat, or making the identity null, is caught by the co-located proof. Widening the guard to >= survives — but it survives on main too, so that is a pre-existing boundary gap, not something this PR introduces.

The association-order analysis from the last round still stands and I did not redo it; nothing in this delta touches the fold.

Re-reviewed at ada2e039 (previously commented at 8ece6666). Baseline origin/main = 725129fe.

The blocking finding is fixed. foldAbsorbing restores the early exit, and I re-ran the exact experiment.

Non-termination — resolved

Unbounded lazy List of 32-bit vectors (cap crossed at element 32 769), counting pulls:

All four affected exports on both orders now return, with the same result as main, in under 2x the pulls. At 8ece6666 the same probe was still pulling at 54.7M elements after 15 s and never returned.

The two numbers the foldAbsorbing JSDoc cites reproduce exactly: 65 536 elements read for a cap crossed at 32 769, and 4 read for a cap crossed at 3 (maxLength/2-sized elements — main reads 3). The "at most one doubling" bound holds in every case I measured.

Results unchanged for non-overflowing input

380 comparisons of PR output against main, all identical:

• element widths 0–5 bits x lengths 0–40, both bit orders;
• mixed-width elements, lengths 0–30;
• maxLength boundary: 60–68 elements of maxLength/64; and [vec(maxLength-1+d), vec(1)] for d in -2..2, i.e. exactly at, just under and just over the cap;
• cap crossed at every run-boundary position: 1–40 elements of maxLength/16;
• tryU8ListToVec lengths 0–40 and at maxLength/8 -2..+2 bytes;
• the throwing u8ListToVec wrapper at and past the cap.

Cost claim re-derived at n=20k, non-overflowing (best of 4 after warmup): tryListToVec 6.3 ms on main vs 5.6 ms here; tryU8ListToVec 4.4 vs 3.8. "At the same cost as the accumulator they replace" measures true.

Rest of the battery

• npx tsc --noEmit 0 on both trees.
• npm run prepack 0 from a freshly cleaned tree, both trees.
• npm test: 2651 pass / 0 fail here vs 2646 / 0 on main — +5, matching the new foldAbsorbing proofs and tryListToVecUnbounded.
• Public surface (dual-axis, from emitted declarations): exactly two const changes — foldAbsorbing added as <T>({ monoid, absorbing }: Absorbing<T>) => (list: List<T>) => T, and fold's parameter rendered as monoid: Monoid<T> instead of the destructured form (same type). Types: +Absorbing, +_Run, -_ListToVecOp, -_ListToVecState. No signature widened to any. _Run correctly _-prefixed; Absorbing is genuinely public since it is in foldAbsorbing's signature.
• @module survives emit in both module.f.d.mts and types.d.ts; no elided or any in the monoid declarations.
• Broken-link sets identical to main — deleting types/bit_vec/todo/listtovec-overflow-early-exit.md stranded nothing.

Mutation tests on the new code, each verified to have landed on the expression and not a JSDoc line:

• next.value === absorbing → false (never stop): 2 failures. Killed.
• result === null ? absorbing : result → result: killed by tsc (Nullable<T> not assignable to T).
• absorbing: null → absorbing: unpackEmpty in tryUnpackConcat: 18 failures. Killed.
• push(monoid.operation)(1) → (2) in absorbingAccumulator: survived, but this is an equivalent mutant — run sizes are only ever compared for equality, so seeding at 2 produces the identical merge tree. Not a coverage gap.

Two nits, neither blocking

1. foldAbsorbing reads tryFold's null as "stopped", but tryFold also returns end(state) unchanged, so a monoid whose T includes null with a non-null absorbing element would get absorbing where fold returns null. Unreachable in this repo — bit_vec is the only user and its absorbing element is null, so the two agree — and my sweep confirms it. Worth a line in the JSDoc if foldAbsorbing ever grows a second caller.

2. absorbingAccumulator builds push(monoid.operation)(1) itself where the file already has step = operation => push(operation)(1) one screen up. const p = step(monoid.operation) would say the same thing and keep the seed in one place.

Approving.

Re-reviewed at 6fafb913, baseline origin/main = 725129fe (unchanged). Previously approved at ada2e039; the delta is one commit, "Review nits: make the tryFold signal unambiguous, share the run seed", touching fjs/common/monoid/module.f.mjs (+37/-10) and proof.f.mjs (+21). Both non-blocking nits from the last round are addressed, and both fixes are correct rather than merely responsive. Approving again.

Because monoid moved, I re-ran the non-termination experiment from scratch rather than carrying the previous result forward.

Non-termination: re-verified, not carried forward

Unbounded lazy list whose prefix overflows maxLength, all four exports on both bit orders, with a pull counter that throws past 20M pulls:

Same results as main everywhere, under 2× the pulls, matching the ada2e039 numbers exactly. Negative control: the same probe against the earlier broken head 8ece6666 hits the 20M cap without returning (~4.8 s per case), so the probe does detect the regression it is meant to detect.

Nit 1 — tryFold's stop-null vs a legitimate null result

Fixed properly, by making the signal unambiguous at the type level rather than by documenting the hazard away: the accumulator's end now yields readonly[T], so tryFold returning null can only mean "stopped", and foldAbsorbing destructures the tuple. One allocation per fold, not per element, as the comment says.

The new nullValued proof is a real test, not decoration. A partial revert (end: c alone) is killed by tsc (TS2322 at both sites). A type-coherent full revert to the ada2e039 shape — third type param back to T, end: c, return result === null ? absorbing : result — compiles and then fails at runtime: proof.foldAbsorbing.nullValued(): error, 2651 pass / 1 fail. The killing case is foldAbsorbing(min)([]), where the old code folded to the null identity and misread it as an abandoned walk, returning the absorbing 0.

I also re-derived the new JSDoc claim that foldAbsorbing(a)(list) and fold(a.monoid)(list) agree on every finite list including null-valued ones: 3,000 randomized lists over the min monoid (lengths 0–40, ~20% null elements, ~10% absorbing 0), 0 mismatches under Object.is.

Nit 2 — absorbingAccumulator re-deriving push(op)(1)

Also fixed correctly, and the type split it required is load-bearing rather than cosmetic. step is now typed as returning _Run<T> (non-nullable) so absorbingAccumulator can read next.value, and foldStep = step is the checked widening to Fold<T, _Stack<T>> that list.fold takes. Retyping step's result back to _Stack<T> produces TS18047: 'next' is possibly 'null', so the narrower type is genuinely carrying the "only the newest run can be absorbing" invariant into the checker.

Gates

• npx tsc --noEmit — exit 0.
• npm run prepack from a clean tree — exit 0.
• npm test — 2652 pass / 0 fail, vs 2646 on main. +6, of which the new nullValued proof is one.
• Public surface unchanged: foldAbsorbing: <T>({ monoid, absorbing }: Absorbing<T>) => (list: List<T>) => T, no elided or any in the emitted declarations. The readonly[T] stays internal.
• Link check — broken-link set byte-identical to main.
• CHANGELOG untouched by this delta, correctly: the entries for common/monoid and types/bit_vec already cover the released behaviour, and nothing here changes it.

Everything settled at ada2e039 and untouched by this delta (the 380 PR-vs-main behaviour comparisons, the cost measurements, association order across the six Monoid instances, the earlier mutation battery) I did not redo.

No findings. LGTM.

Re-reviewed after the merge of origin/main (e2199caf). Still approving.

What actually moved since 6fafb913: one merge commit. fjs/common/monoid/ is
byte-identical (git diff 6fafb913..5d7d0260a367ef558ecee722993129ece28c1f6f -- fjs/common/monoid is empty). The only
change reaching this PR's files is #1545's @import sweep relocating the tags in
types/bit_vec/module.f.mjs and proof.f.mjs into the leading JSDoc block — comment
placement, no executable statement touched. Merge-base is now origin/main exactly.

Because types/bit_vec moved at all, I re-ran the load-bearing non-termination
experiment from scratch at this head rather than carrying the numbers forward,
negative control included.

Non-termination probe — unbounded lazy Thunk list whose prefix overflows
maxLength (1_048_576), counting pulls, 20M cap:

All eight — tryListToVec/listToVec/tryU8ListToVec/u8ListToVec on both lsb
and msb — terminate with results identical to main (null from the try* pair,
throw from the mapUnwrap pair), at 1.99998× main's pulls. The negative control
confirms the probe can still detect the regression: the same script on 8ece6666
hits the cap on all eight. foldAbsorbing's early exit is intact.

Rest of the battery at this head:

• npx tsc --noEmit — exit 0.
• npm run prepack from a cleaned tree — exit 0 (both passes).
• npm test — 2652 pass / 0 fail, vs 2646 on origin/main; the +6 are the new
  common/monoid and bit_vec proofs.
• Public surface (dual-axis, both trees prepacked) — unchanged from what was settled
  last round: +Absorbing<T>, +_Run<T>, +foldAbsorbing, -_ListToVecOp,
  -_ListToVecState, and fold's emitted parameter renamed from the destructuring
  pattern to monoid (same type). No signature widened to any.
  Absorbing being unprefixed is correct, not a §6.2 miss: it is the parameter type
  of the public foldAbsorbing, so it has to be public — the _ prefix is for
  implementation-only types, and _Run correctly carries one.
• @module survives declaration emit in bit_vec/module.f.d.mts,
  monoid/module.f.d.mts and monoid/types.d.ts (1 each) — the @import relocation
  did not fold the header into import trivia. No elided or any in either.
• Link check — broken-link set is identical to main's, not merely the same count.
• CHANGELOG — the two Unreleased entries link only /pull/1548. No
  **BREAKING CHANGES:** prefix, which I still read as right: every input I tested
  gives main's answer, and the one genuine difference (number.sum reassociating, so
  float rounding may differ) is stated in the entry itself.

Everything settled at 6fafb913 — end yielding readonly [T], step retyped to
non-nullable _Run<T> (reverting it reintroduces TS18047, so it is load-bearing),
and the 3,000-list randomized foldAbsorbing-vs-fold agreement — stands on code
that has not changed a byte since.