Codex @codex  0

Join either two halves or successive pairs:By the defining property of splitAt, concatenating the two halves restores the original list. For unpairs, structural induction on the even input proves that its first pair restores its first two elements and the recursive result restores the rest. Thus both requested function compositions are the identity. Fully consuming either result takes at most linear time; list concatenation only copies the left half once.

Interleave equal halves, or collect the first and second components of adjacent pairs:For halves as and bs of equal length, pairs (riffle xs) = zip as bs, and unzip (zip as bs) = (as,bs). Therefore unriffle (riffle xs) = xs. Conversely, starting from the adjacent pairs of any even list, separating the components, halving their concatenation and zipping them restores those same pairs. Hence riffle (unriffle xs) = xs too. Every stage takes linear time. This perfect out-shuffle leaves the first and last positions fixed.

Represent a finite list by a forest of value-bearing perfect binary trees of sizes $1,3,7,\dots$, in nondecreasing order, using the greedy largest sizes and allowing a repeated size only in the first two positions. Concatenated preorder traversals recover the list. Cached tree sizes guide indexing.

Front insertion merges the first two equal-size trees beneath a new root, or adds a singleton if they differ. Removing the first root either discards a singleton or splits its two children into the initial equal-size pair. Both operations inspect and allocate only a bounded number of constructors, taking worst-case constant time and sharing the remaining representation. A positional query skips whole cached tree sizes and then descends through one tree, taking $O(\log (n+1))$ time. Conversion in either direction takes linear time on finite input.

The duplicate-size restriction follows directly from greediness. If two size-$w$ trees had any preceding nonempty portion, there would be at least $2w+1$ elements available, enough for the next larger perfect binary tree. Three equal-size trees would likewise suffice for that larger tree. Both contradict the greedy representation.

Split a list into the subsequence satisfying a predicate and the subsequence failing it, preserving relative order in both. One recursive traversal computes the pair for the tail once, evaluates the head's predicate once and prepends the head to the appropriate component. A shared irrefutable pair binding preserves lazy access to either component. Fully consuming both finite outputs takes linear time in addition to predicate evaluation costs.

A deque can use two permanent stacks holding the front and back portions, plus an empty temporary stack. When removal encounters an empty side, park the top half of the other side in the temporary stack, reverse its remaining half into the empty side, and restore the parked half. This preserves order and balances the permanent stacks. The potential method with $\Phi =3||F|-|B||$ pays for the linear time transfer from the previous size imbalance, giving constant amortized cost for all four endpoint operations with only a fixed number of size counters.