AFTD Auto-Formalizing Theoretical Domains

comparison_tree_eval

def

Given an assignment v : Fin n → α of values in a linearly ordered type α, evaluate a comparison tree: on a leaf leaf ans, return the index ans; on a branch branch i j l r, if v i < v j strictly, recursively evaluate the left subtree l on v, otherwise recursively evaluate the right subtree r on v.

Statement

def comparison_tree_eval {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α) :
    ComparisonTree n → Fin n
Defined in
arXiv:2610.18740 Sec. 3.1
Verified
18 Oct 2026
Axioms
none listed
Built on 3
  • ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
  • LinearOrder.toTotalPreorderEvery LinearOrder is a TotalPreorder.
  • TotalPreorderA total preorder: a preorder where ≤ is total (complete). This is weaker than LinearOrder — it does NOT require antisymmetry or…
Used by 8

Read back from the Lean

Given a natural number n, a type α equipped with a linear order LinearOrder α, and a vector v : Fin n → α, comparison_tree_eval v defines a function from ComparisonTree n to Fin n by structural recursion: - On .leaf ans, it returns ans : Fin n. - On .branch i j l r (with i, j : Fin n and subtrees l, r : ComparisonTree n), it evaluates v i < v j: if true, it recursively evaluates comparison_tree_eval v l; otherwise, it recursively evaluates comparison_tree_eval v r.

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

/-- Evaluation of a comparison decision tree on an assignment of linearly ordered values. -/
def comparison_tree_eval {n : ℕ} {α : Type*} [LinearOrder α] (v : Fin n → α) :
    ComparisonTree n → Fin n := fun
  | .leaf ans => ans
  | .branch i j l r =>
      if v i < v j then comparison_tree_eval v l else comparison_tree_eval v r
See it in the graphDiscuss this resultChallenge it