Source lean/Determinize/Proof/FiniteModel/Lookup.lean
namespace Determinize.Proof.FiniteModelinductive Lookup (α : Type) where  | value (entry : α)  | branch (split : Nat) (left right : Lookup α)def Lookup.get (table : Lookup α) (i : Nat) : α :=  match table with  | .value entry => entry  | .branch split left right => if i < split then left.get i else right.get idef Lookup.Indexed (table : Lookup α) (label : α → Nat) (lo hi : Nat) : Prop :=  match table with  | .value entry => hi = lo + 1 ∧ label entry = lo  | .branch split left right =>    lo < split ∧ split < hi ∧ left.Indexed label lo split ∧ right.Indexed label split hiprivate def indexedDecidable (table : Lookup α) (label : α → Nat) (lo hi : Nat) :    Decidable (table.Indexed label lo hi) :=  match table with  | .value _ => inferInstanceAs (Decidable (_ ∧ _))  | .branch split left right =>    letI := indexedDecidable left label lo split    letI := indexedDecidable right label split hi    inferInstanceAs (Decidable (_ ∧ _ ∧ _ ∧ _))instance (table : Lookup α) (label : α → Nat) (lo hi : Nat) :    Decidable (table.Indexed label lo hi) := indexedDecidable table label lo hitheorem Lookup.get_index (table : Lookup α) (label : α → Nat) (lo hi : Nat)    (valid : table.Indexed label lo hi) (i : Nat) (lower : lo ≤ i) (upper : i < hi) :    label (table.get i) = i := by  induction table generalizing lo hi with  | value a =>    have endEq := valid.1    have h : i = lo := by omega    exact valid.2.trans h.symm  | branch split left right ihLeft ihRight =>    by_cases before : i < split    · simpa [Lookup.get, before] using ihLeft lo split valid.2.2.1 lower before    · simpa [Lookup.get, before] using        ihRight split hi valid.2.2.2 (by omega) uppertheorem lookup_evidence_all {n : Nat} (p : Fin n → Prop)    (table : Lookup (Subtype p))    (indexed : table.Indexed (fun e ↦ e.val.val) 0 n) : ∀ i, p i := by  intro i  have same := table.get_index (fun e ↦ e.val.val) 0 n indexed i.val (Nat.zero_le _) i.isLt  have index : (table.get i.val).val = i := Fin.ext same  exact index ▸ (table.get i.val).propertyend Determinize.Proof.FiniteModel