Source lean/Determinize/Proof/FiniteModel/SparseQueries.lean
import Determinize.Proof.FiniteModel.IndexedReplayimport Determinize.Proof.FiniteModel.Terminationnamespace Determinize.Finiteopen Spec.FiniteModel Proof.FiniteModeldef edgeValues {n : Nat} (edges : List Edge) (values : Fin n → Rat) : Rat :=  (edges.map fun edge ↦    if h : edge.target < n then edge.probability * values ⟨edge.target, h⟩ else 0).sumprivate theorem sum_edge_values {n : Nat} (edges : List Edge) (values : Fin n → Rat)    (bounded : ∀ edge ∈ edges, edge.target < n) :    (∑ j : Fin n, (edges.map fun edge ↦ if edge.target = j.val then edge.probability else 0).sum *      values j) =      edgeValues edges values := by  induction edges with  | nil => simp [edgeValues]  | cons edge edges ih =>    have bound := bounded edge (by simp)    have rest := ih (fun e h ↦ bounded e (by simp [h]))    simp only [List.map_cons, List.sum_cons, add_mul, Finset.sum_add_distrib, rest,      edgeValues, List.map_cons, List.sum_cons, dite_eq_left bound]    congr 1    have eq (j : Fin n) : edge.target = j.val ↔ (⟨edge.target, bound⟩ : Fin n) = j := by      constructor      · intro h; apply Fin.ext; exact h      · intro h; exact congrArg Fin.val h    simp only [ite_mul, zero_mul, eq]    simptheorem Candidate.weighted_sum (candidate : Candidate) (i : Fin candidate.states.size)    (edges : candidate.EdgesValid i) (values : Fin candidate.states.size → Rat) :    (∑ j, candidate.weight i j * values j) = edgeValues (candidate.row i).edges.toList values :=  sum_edge_values _ _ (fun edge present ↦ (edges.2 edge present).1)private def SparseEquation (candidate : Candidate) (kind : Fin candidate.states.size → StateKind)    (values : Fin candidate.states.size → Rat) (state : Fin candidate.states.size) : Prop :=  values state = match kind state with    | .returned r => r | .rejected => 0    | .transient => edgeValues (candidate.row state).edges.toList valuesprivate instance (candidate : Candidate) (kind : Fin candidate.states.size → StateKind)    (values : Fin candidate.states.size → Rat) (state : Fin candidate.states.size) :    Decidable (SparseEquation candidate kind values state) := inferInstanceAs (Decidable (_ = _))def Candidate.QueryStateValid (candidate : Candidate)    (valid : candidate.GraphValid)    (certificate : TerminationCertificate (candidate.graphModel valid))    (state : Fin candidate.states.size) : Prop :=  (certificate.output.dead state = true → (candidate.row state).kind = .transient ∧    ∀ next, 0 < candidate.weight state next → certificate.output.dead next = true) ∧  ((cut (candidate.graphModel valid) certificate.output.dead).kind state = .transient →    0 < candidate.weight state (certificate.output.next state) ∧      certificate.output.rank (certificate.output.next state) < certificate.output.rank state) ∧  (∀ moment, SparseEquation candidate    (certificate.output.model (candidate.graphModel valid) moment).kind    (certificate.output.values moment) state) ∧  SparseEquation candidate    (rejectionQuery (candidate.graphModel valid) certificate.output.dead).kind    certificate.rejection stateinstance (candidate : Candidate)    (valid : candidate.GraphValid)    (certificate : TerminationCertificate (candidate.graphModel valid))    (state : Fin candidate.states.size) :    Decidable (candidate.QueryStateValid valid certificate state) :=  inferInstanceAs (Decidable (_ ∧ _ ∧ _ ∧ _))theorem sparseResults_valid (candidate : Candidate)    (valid : candidate.GraphValid)    (certificate : TerminationCertificate (candidate.graphModel valid))    (states : ∀ state, candidate.QueryStateValid valid certificate state) :    certificate.Valid (candidate.graphModel valid) := by  apply terminationStates_valid  intro state  refine ⟨(states state).1, (states state).2.1, ?_, ?_⟩  · intro moment    change certificate.output.values moment state =        match (certificate.output.model (candidate.graphModel valid) moment).kind state with      | .returned r => r | .rejected => 0      | .transient => ∑ next, candidate.weight state next * certificate.output.values moment next    rw [candidate.weighted_sum state (valid.edges state)]    exact (states state).2.2.1 moment  · change certificate.rejection state =        match (rejectionQuery (candidate.graphModel valid) certificate.output.dead).kind state with      | .returned r => r | .rejected => 0      | .transient => ∑ next, candidate.weight state next * certificate.rejection next    rw [candidate.weighted_sum state (valid.edges state)]    exact (states state).2.2.2end Determinize.Finite