functionalscript · sergey-shandar · Aug 15, 2026 · Aug 15, 2026 · Aug 15, 2026 · Aug 15, 2026
diff --git a/changelog/unreleased/1582.md b/changelog/unreleased/1582.md
@@ -0,0 +1,2 @@
+- `types/patricia_trie`: `end` is a right fold over the candidate stack and
+  `push` splits instead of indexing; identical output
diff --git a/fjs/types/patricia_trie/module.f.mjs b/fjs/types/patricia_trie/module.f.mjs
@@ -6,6 +6,8 @@
  * @import { Candidate, Create, PatriciaTrie } from './types.ts'
  */
 
+import { splitLast } from '../array/module.f.mjs'
+
 /**
  * Creates a Patricia trie whose node merging is delegated to `create`.
  *
@@ -14,24 +16,37 @@
 export const patriciaTrie = create => ({
     push: (c, [storage, stack]) => {
         const [u] = c
-        while (stack.length >= 2) {
-            const [rLeaf, rHash] = stack[stack.length - 1]
-            const [lLeaf, lHash] = stack[stack.length - 2]
+        // Carry propagation: merge the top two candidates for as long as they
+        // are more tightly coupled to each other than the right one is to the
+        // incoming leaf. Genuinely sequential — each merge decides whether the
+        // next one happens — so the loop stays, but the stack is read by
+        // splitting rather than by index arithmetic. Either split answering
+        // `null` means fewer than two candidates are left, which is where the
+        // old `stack.length >= 2` guard stopped.
+        while (true) {
+            const top = splitLast(stack)
+            if (top === null) { break }
+            const [belowR, [rLeaf, rHash]] = top
+            const below = splitLast(belowR)
+            if (below === null) { break }
+            const [rest, [lLeaf, lHash]] = below
             if ((lLeaf ^ rLeaf) >= (rLeaf ^ u)) { break }
             const [h, newS] = create(lHash, rHash, storage)
             storage = newS
-            stack = [...stack.slice(0, -2), [rLeaf, h]]
+            stack = [...rest, [rLeaf, h]]
         }
         return [storage, [...stack, c]]
     },
+    // Drain the right spine into a root: a right fold whose seed is the last
+    // candidate's identity. `splitLast` supplies both halves at once, so the
+    // empty stack is the `null` branch rather than a separate length guard.
     end: ([storage, stack]) => {
-        if (stack.length === 0) { return [undefined, storage] }
-        let h = stack[stack.length - 1][1]
-        for (let i = stack.length - 2; i >= 0; i--) {
-            const lHash = stack[i][1];
-            [h, storage] = create(lHash, h, storage)
-        }
-        return [h, storage]
+        const split = splitLast(stack)
+        if (split === null) { return [undefined, storage] }
+        const [rest, [, lastHash]] = split
+        return rest.reduceRight(
+            ([h, s], [, lHash]) => create(lHash, h, s),
+            /** @type {readonly [typeof lastHash, typeof storage]} */([lastHash, storage]))
     }
 })
 

diff --git a/fjs/types/patricia_trie/todo/declarative-stack-fold.md b/fjs/types/patricia_trie/todo/declarative-stack-fold.md
Original file line number	Diff line number	Diff line change
		@@ -0,0 +1,2 @@
		- `types/patricia_trie`: `end` is a right fold over the candidate stack and
		`push` splits instead of indexing; identical output