west_stack_sort
West's stack-sorting map s acts on a list by maintaining an auxiliary stack, popping elements strictly smaller than the next input element to the output before pushing, and popping the remaining stack once the input is exhausted.
Statement
def west_stack_sort {α : Type*} [LinearOrder α] (l : List α) : List α
- Defined in
- arXiv:2610.32824 Section 1
- Verified
- 26 Oct 2026
- Axioms
- none listed
- Built on 2
- TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or… - LinearOrder.toTotalPreorderEvery
LinearOrderis aTotalPreorder.
- TotalPreorderA total preorder: a preorder where
Read back from the Lean
The definition west_stack_sort takes a type α with a linear order [LinearOrder α] and a list l : List α, and returns a List α.
It is defined as aux l [], where the auxiliary function aux : List α → List α → List α processes the remaining input list and a stack:
1. aux [] stack = stack: when the input list is empty, it returns the stack as is.
2. aux (x :: xs) [] = aux xs [x]: when the stack is empty, the first element x of the input list is pushed onto the stack.
3. aux (x :: xs) (s :: stack):
- If s < x, it emits s and recurses with s :: aux (x :: xs) stack (popping the stack while keeping the input list unchanged).
- If ¬(s < x) (i.e., s ≥ x), it pushes x onto the stack and recurses with aux xs (x :: s :: stack).
Termination is by well-founded recursion on the lexicographic pair (input.length, stack.length).
Written by a model that saw only the Lean, never the English above. If the two disagree, that is worth a challenge.
Lean source view module on GitHub
/-- West's stack-sorting operator on lists of linearly ordered elements. -/ def west_stack_sort {α : Type*} [LinearOrder α] (l : List α) : List α := aux l [] where aux : List α → List α → List α | [], stack => stack | x :: xs, [] => aux xs [x] | x :: xs, s :: stack => if s < x then s :: aux (x :: xs) stack else aux xs (x :: s :: stack) termination_by xs stack => (xs.length, stack.length)