Documentation

ToCslib.Order.PrefixRecursion

Recurrences depending on earlier coordinates #

Each coordinate may inspect only its strict prefix. Over a well-founded order of coordinates, such equations have at most one solution (Function.UsesPrefix.fixedPoint_unique); the coordinates can be Fin n, or ℕ for a stream. Over Fin n the solution is computed by well-founded recursion. When the coordinate operations are continuous, this solution is also their least fixed point. The values may themselves contain partial information or errors.

@[irreducible]
def Function.prefixRecursion {n : ℕ} {α : Type u_2} (step : (i : Fin n) → (Fin ↑i → α) → α) (i : Fin n) :
α

Compute a finite recurrence using only already computed coordinates.

Equations
Instances For
    theorem Function.prefixRecursion_apply {n : ℕ} {α : Type u_2} (step : (i : Fin n) → (Fin ↑i → α) → α) (i : Fin n) :
    prefixRecursion step i = step i fun (j : Fin ↑i) => prefixRecursion step ⟨↑j, ⋯⟩

    Unfold one coordinate without expanding the preceding computations.

    def Function.UsesPrefix {ι : Type u_1} {α : Type u_2} [LT ι] (f : (ι → α) → ι → α) :

    Coordinate i depends only on coordinates strictly before i.

    Equations
    Instances For
      theorem Function.UsesPrefix.fixedPoint_unique {ι : Type u_1} {α : Type u_2} [LT ι] [WellFoundedLT ι] {f : (ι → α) → ι → α} (hf : UsesPrefix f) {x y : ι → α} (hx : f x = x) (hy : f y = y) :
      x = y

      A prefix-dependent system over well-founded coordinates has at most one solution, even with partial values.

      def OmegaCompletePartialOrder.ContinuousHom.prefixMap {n : ℕ} {D : Type u_1} [OmegaCompletePartialOrder D] (step : (i : Fin n) → (Fin ↑i → D) →𝒄 D) :
      (Fin n → D) →𝒄 Fin n → D

      Assemble continuous operations on strict prefixes into simultaneous equations.

      Equations
      Instances For

        The assembled equations depend only on earlier coordinates.

        theorem OmegaCompletePartialOrder.ContinuousHom.prefixMap_prefixRecursion {n : ℕ} {D : Type u_1} [OmegaCompletePartialOrder D] (step : (i : Fin n) → (Fin ↑i → D) →𝒄 D) :
        (prefixMap step) (Function.prefixRecursion fun (i : Fin n) => ⇑(step i)) = Function.prefixRecursion fun (i : Fin n) => ⇑(step i)

        Well-founded evaluation satisfies the simultaneous equations.

        theorem OmegaCompletePartialOrder.ContinuousHom.prefixMap_fix {n : ℕ} {D : Type u_1} [OmegaCompletePartialOrder D] [OrderBot D] (step : (i : Fin n) → (Fin ↑i → D) →𝒄 D) :
        (prefixMap step).fix = Function.prefixRecursion fun (i : Fin n) => ⇑(step i)

        The least fixed point of finite prefix equations is their computed solution.