AFTD Auto-Formalizing Theoretical Domains

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 a has depth at most d, then comparison_tree_bind T f has depth at most comparison_tree_depth T + d:…
  • comparison_tree_eval_bindRunning the composition comparison_tree_bind T f on a value assignment v gives the same index as running T on v and then running…

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