comparison_tree_bind
def
Composition of comparison decision trees: run T, and at each leaf a continue with the tree f a. Recursion peels off the first stage and appends a continuation stage below each leaf.
Statement
def comparison_tree_bind {n : ℕ} : ComparisonTree n → (Fin n → ComparisonTree n) → ComparisonTree n- Source
- step towards v_selection_16_8_upper_bound
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 1
- ComparisonTreeA binary comparison decision tree on n elements whose internal nodes perform pairwise comparisons and whose leaves return an element index.
- Used by 2
- comparison_tree_depth_bind_leIf every continuation tree
f ahas depth at mostd, thencomparison_tree_bind T fhas depth at mostcomparison_tree_depth T + d:… - comparison_tree_eval_bindRunning the composition
comparison_tree_bind T fon a value assignmentvgives the same index as runningTonvand then running…
- comparison_tree_depth_bind_leIf every continuation tree
Lean source view module on GitHub
/-- Sequential composition of comparison trees: `comparison_tree_bind T f` runs the first stage `T` and then the continuation `f a` selected by the returned index. -/ def comparison_tree_bind {n : ℕ} : ComparisonTree n → (Fin n → ComparisonTree n) → ComparisonTree n := fun T f => match T with | .leaf a => f a | .branch i j l r => .branch i j (comparison_tree_bind l f) (comparison_tree_bind r f)