comparison_tree_eval
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
LinearOrderis aTotalPreorder. - TotalPreorderA total preorder: a preorder where
≤is total (complete). This is weaker thanLinearOrder— it does NOT require antisymmetry or…
- Used by 8
- v_selection_three_two_upper_boundThe 2nd smallest (the median) of 3 distinct elements can be found using at most 3 pairwise comparisons, that is, V_2(3) ≤ 3.
- comparison_tree_selects_rank_existsFor every n and every rank r : Fin n there exists a comparison decision tree on n elements that correctly selects the element of rank r.
- comparison_tree_correct_for_selectionGiven a natural number n, a partial order P on Fin n, a rank i, and a comparison tree t on n elements, t correctly selects the i-th…
- comparison_tree_selects_rankA comparison decision tree T on n elements (T : ComparisonTree n) correctly selects the element of rank r : Fin n if for every permutation…
- comparison_tree_eval_bindRunning the composition
comparison_tree_bind T fon a value assignmentvgives the same index as runningTonvand then running… - comparison_tree_correct_for_selection_existsFor every natural number n, strict partial order P on Fin n, and rank 1 ≤ i ≤ n, there exists a comparison decision tree on n elements…
- not_comparison_tree_selects_rank_two_leaf_oneFor n = 2, the leaf comparison decision tree returning index 0 does not correctly select rank 1.
- comparison_tree_selects_rank_one_zeroFor n = 1, the single leaf comparison decision tree returning index 0 correctly selects rank 0.
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