tarski_query_tree_bind
def
Sequential composition of query trees: run the tree, then feed its output point into the continuation g to obtain the tree that is actually executed.
Statement
def tarski_query_tree_bind {n k : ℕ} (g : (Fin k → Fin n) → TarskiQueryTree n k) :
TarskiQueryTree n k → TarskiQueryTree n k- Source
- step towards tarski_query_complexity_five_le_log_sq
- Verified
- 18 Oct 2026
- Axioms
- none listed
- Built on 1
- TarskiQueryTreeA deterministic adaptive query algorithm for an unknown map f : [n]^k → [n]^k, as a decision tree: a leaf outputs a point; an internal…
- Used by 2
- tarski_box_query_le_succ_halvingOne dimension costs a factor log₂ n: from a box-search algorithm in dimension k with q queries one gets one in dimension k+1 with at most…
- tarski_query_tree_bind_specRun/cost law for sequential composition: the run of a bind is the run of the continuation g at the output of the first tree, and the cost…
Lean source view module on GitHub
/-- Sequential composition: run a query tree, then continue with the tree g applied to its output. -/ def tarski_query_tree_bind {n k : ℕ} (g : (Fin k → Fin n) → TarskiQueryTree n k) : TarskiQueryTree n k → TarskiQueryTree n k := fun _t => match _t with | .output x => g x | .query x k' => .query x (fun v => tarski_query_tree_bind g (k' v))