AFTD Auto-Formalizing Theoretical Domains

submod_query_tree_eval

def

Evaluates a query decision tree on a function f by querying coordinates along the tree path until reaching a leaf.

Statement

def submod_query_tree_eval {n k d : ℕ} (T : SubmodQueryTree n k d) (f : CubeFunc n k) : Bool
Defined in
arXiv:2611.02374, Def. 2.5
Verified
06 Nov 2026
Axioms
none listed
Built on 2
  • CubeFuncThe type of functions from the n-dimensional Boolean hypercube {0, 1}^n into {0, 1, ..., k}, represented by Fin (k + 1).
  • SubmodQueryTreeAn adaptive deterministic query decision tree of depth at most d for testing functions on the Boolean hypercube into {0, ..., k}.
Used by 1

Read back from the Lean

The function submod_query_tree_eval evaluates a query tree T : SubmodQueryTree n k d on an input function f : (Fin n → Bool) → Fin (k + 1), returning a Bool. It is defined by recursion on the tree T: - If T is a leaf node leaf b, it returns the boolean label b. - If T is a query node query x next, it evaluates f at the hypercube point x : Fin n → Bool to obtain an index f x : Fin (k + 1), and then recursively evaluates the child tree next (f x) on f.

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

/-- Evaluate a query decision tree on a function from the hypercube. -/
def submod_query_tree_eval {n k d : ℕ} (T : SubmodQueryTree n k d) (f : CubeFunc n k) : Bool := match T with
  | .leaf b => b
  | .query x next => submod_query_tree_eval (next (f x)) f
See it in the graphDiscuss this resultChallenge it