Improvable lower bounds.

The typeclass Estimator a ε, where a : Thunk α and ε : Type, states that e : ε carries the data of a lower bound for a.get, in the form bound_le : bound a e ≤ a.get, along with a mechanism for asking for a better bound improve e : Option ε, satisfying

match improve e with
| none => bound e = a.get
| some e' => bound e < bound e'

i.e. it returns none if the current bound is already optimal, and otherwise a strictly better bound.

(The value in α is hidden inside a Thunk to prevent evaluating it: the point of this typeclass is to work with cheap-to-compute lower bounds for expensive values.)

An appropriate well-foundedness condition would then ensure that repeated improvements reach the exact value.

class EstimatorData {α : Type u_1} (a : Thunk α) (ε : Type u_3) : Type (max u_1 u_3)

Given [EstimatorData a ε]

• a term e : ε can be interpreted via bound a e : α as a lower bound for a, and
• we can ask for an improved lower bound via improve a e : Option ε.

The value a in α that we are estimating is hidden inside a Thunk to avoid evaluation.

• bound : ε → α

  The value of the bound for a representation by a term of ε.

• improve : ε → Option ε

  Generate an improved lower bound.

class Estimator {α : Type u_1} [Preorder α] (a : Thunk α) (ε : Type u_3) extends EstimatorData a ε : Type (max u_1 u_3)

Given [Estimator a ε]

• we have bound a e ≤ a.get, and
• improve a e returns none iff bound a e = a.get, and otherwise it returns a strictly better bound.

• bound : ε → α
• improve : ε → Option ε
• bound_le (e : ε) : EstimatorData.bound a e ≤ a.get

  The calculated bounds are always lower bounds.

• improve_spec (e : ε) : match EstimatorData.improve a e with | none => EstimatorData.bound a e = a.get | some e' => EstimatorData.bound a e < EstimatorData.bound a e'

  Calling improve either gives a strictly better bound, or a proof that the current bound is exact.

@[reducible, inline]

abbrev Estimator.trivial {α : Type u} (a : α) : Type u

A trivial estimator, containing the actual value.

Equations

• Estimator.trivial a = { b : α // b = a }

instance instBotTrivial {α : Type u_1} {a : α} : Bot (Estimator.trivial a)

Equations

• instBotTrivial = { bot := ⟨a, ⋯⟩ }

instance instWellFoundedGTUnit : WellFoundedGT Unit

instance instWellFoundedGTTrivial {α : Type u_1} [Preorder α] (a : α) : WellFoundedGT (Estimator.trivial a)

instance instEstimatorPureTrivial {α : Type u_1} [Preorder α] {a : α} : Estimator (Thunk.pure a) (Estimator.trivial a)

Equations

• instEstimatorPureTrivial = { bound := fun (b : Estimator.trivial a) => ↑b, improve := fun (x : Estimator.trivial a) => none, bound_le := ⋯, improve_spec := ⋯ }

@[irreducible]

def Estimator.improveUntilAux {α : Type u_1} {ε : Type u_2} [Preorder α] (a : Thunk α) (p : α → Bool) [Estimator a ε] [WellFoundedGT ↑(Set.range (EstimatorData.bound a))] (e : ε) (r : Bool) : Except (Option ε) ε

Implementation of Estimator.improveUntil.

Equations

• One or more equations did not get rendered due to their size.

def Estimator.improveUntil {α : Type u_1} {ε : Type u_2} [Preorder α] (a : Thunk α) (p : α → Bool) [Estimator a ε] [WellFoundedGT ↑(Set.range (EstimatorData.bound a))] (e : ε) : Except (Option ε) ε

Improve an estimate until it satisfies a predicate, or else return the best available estimate, if any improvement was made.

Equations

• Estimator.improveUntil a p e = Estimator.improveUntilAux a p e false

@[irreducible]

theorem Estimator.improveUntilAux_spec {α : Type u_1} {ε : Type u_2} [Preorder α] (a : Thunk α) (p : α → Bool) [Estimator a ε] [WellFoundedGT ↑(Set.range (EstimatorData.bound a))] (e : ε) (r : Bool) : match improveUntilAux a p e r with | Except.error a_1 => ¬p a.get = true | Except.ok e' => p (EstimatorData.bound a e') = true

If Estimator.improveUntil a p e returns some e', then bound a e' satisfies p. Otherwise, that value a must not satisfy p.

theorem Estimator.improveUntil_spec {α : Type u_1} {ε : Type u_2} [Preorder α] (a : Thunk α) (p : α → Bool) [Estimator a ε] [WellFoundedGT ↑(Set.range (EstimatorData.bound a))] (e : ε) : match improveUntil a p e with | Except.error a_1 => ¬p a.get = true | Except.ok e' => p (EstimatorData.bound a e') = true

If Estimator.improveUntil a p e returns some e', then bound a e' satisfies p. Otherwise, that value a must not satisfy p.

Estimators for sums.

instance instEstimatorDataHAddThunkProd {α : Type u_1} [Add α] {a b : Thunk α} (εa : Type u_3) (εb : Type u_4) [EstimatorData a εa] [EstimatorData b εb] : EstimatorData (a + b) (εa × εb)

Equations

• One or more equations did not get rendered due to their size.

@[simp]

theorem bound_def {α : Type u_1} [Add α] {a b : Thunk α} (εa : Type u_3) (εb : Type u_4) [EstimatorData a εa] [EstimatorData b εb] (e : εa × εb) : EstimatorData.bound (a + b) e = EstimatorData.bound a e.1 + EstimatorData.bound b e.2

@[simp]

theorem improve_def {α : Type u_1} [Add α] {a b : Thunk α} (εa : Type u_3) (εb : Type u_4) [EstimatorData a εa] [EstimatorData b εb] (e : εa × εb) : EstimatorData.improve (a + b) e = match EstimatorData.improve a e.1 with | some e' => some (e', e.2) | none => match EstimatorData.improve b e.2 with | some e' => some (e.1, e') | none => none

instance instEstimatorNatHAddThunkProd (a b : Thunk ℕ) {εa : Type u_3} {εb : Type u_4} [Estimator a εa] [Estimator b εb] : Estimator (a + b) (εa × εb)

Equations

• instEstimatorNatHAddThunkProd a b = { toEstimatorData := instEstimatorDataHAddThunkProd εa εb, bound_le := ⋯, improve_spec := ⋯ }

Estimator for the first component of a pair.

structure Estimator.fst {α : Type u_1} {β : Type u_3} [PartialOrder α] [PartialOrder β] (p : Thunk (α × β)) (ε : Type u_4) [Estimator p ε] : Type u_4

An estimator for (a, b) can be turned into an estimator for a, simply by repeatedly running improve until the first factor "improves". The hypothesis that > is well-founded on { q // q ≤ (a, b) } ensures this terminates.

• inner : ε

  The wrapped bound for a value in α × β, which we will use as a bound for the first component.

instance instWellFoundedGTElemRangeBound {α : Type u_1} {ε : Type u_2} [PartialOrder α] [∀ (a : α), WellFoundedGT { x : α // x ≤ a }] {a : Thunk α} [Estimator a ε] : WellFoundedGT ↑(Set.range (EstimatorData.bound a))

instance instEstimatorDataFstProdOfDecidableLTOfWellFoundedGTSubtypeProdLe {α : Type u_1} {β : Type u_3} [PartialOrder α] [PartialOrder β] [DecidableLT α] {a : Thunk α} {b : Thunk β} (ε : Type u_4) [Estimator (a.prod b) ε] [∀ (p : α × β), WellFoundedGT { q : α × β // q ≤ p }] : EstimatorData a (Estimator.fst (a.prod b) ε)

Equations

• One or more equations did not get rendered due to their size.

def Estimator.fstInst {α : Type u_1} {ε : Type u_2} {β : Type u_3} [PartialOrder α] [PartialOrder β] [DecidableLT α] [∀ (p : α × β), WellFoundedGT { q : α × β // q ≤ p }] (a : Thunk α) (b : Thunk β) (i : Estimator (a.prod b) ε) : Estimator a (fst (a.prod b) ε)

Given an estimator for a pair, we can extract an estimator for the first factor.

Equations

• Estimator.fstInst a b i = { toEstimatorData := instEstimatorDataFstProdOfDecidableLTOfWellFoundedGTSubtypeProdLe ε, bound_le := ⋯, improve_spec := ⋯ }