AFTD Auto-Formalizing Theoretical Domains

west_stack_sort

def

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 than LinearOrder — it does NOT require antisymmetry or…
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.

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)
See it in the graphDiscuss this resultChallenge it