Documentation

PolyFun.PFunctor.Handler.CountMat

Handlers certified by count matrices #

A one-shape Diller–Nahm morphism is a lens bang (y^ι') ⇆ y^ι out of the exponential of a polynomial with one position. Its backward map sends each i : ι to a finite multiset over ι', and at finite ι' it is determined by its count matrix ι → ι' → ℕ (Lens.ofCountMat, Lens.countMat_ofCountMat, Lens.ofCountMat_countMat). Read with ι the resources of an interface P and ι' the resources of an interface Q, the entry at (i, j) is the number of units of j that one unit of i demands: the demands d of Handler.Certified.ofDemand, at natural-number values.

A handler P → FreeM Q certified by such a morphism (Handler.CountCertified) is a certified handler whose exchange is the demand map of the cast count matrix (CountCertified.toCertified), which is the vector–matrix product (CountCertified.toCertified_exchange_apply). The lens points from the resources of Q to those of P: the assignment is contravariant. The identity handler is certified by the counit (CountCertified.id), and handlers compose with the co-Kleisli composite of their lenses in the opposite order (CountCertified.comp). The assignment toCertified preserves identities and composition (CountCertified.toCertified_id, CountCertified.toCertified_comp): the composition of exchanges of Handler.Certified.comp at demand maps is the product of count matrices of Lens.countMat_bangComp (Lens.demand_bangComp). A program with use vector u runs through a composite with use vector u times the product of the two count matrices (CountCertified.isChargeBound_liftM_comp).

The correspondence covers demand maps with natural-number entries, which are the count matrices of one-shape morphisms (CountCertified.ofNatDemand). A demand map with entries outside the image of ℕ, such as an expected demand in ℝ≥0 or an unbounded demand ⊤ in ℕ∞, is not a count matrix, and a certified handler whose exchange is not a demand map has no count matrix at all.

One-shape Diller–Nahm morphisms and their count matrices #

def PFunctor.Lens.ofCountMat {ι : Type u} {ι' : Type u'} [Fintype ι'] (d : ι → ι' → ℕ) :

The one-shape Diller–Nahm morphism with count matrix d: the direction i demands each direction j with multiplicity d i j.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    @[simp]
    theorem PFunctor.Lens.countMat_ofCountMat {ι : Type u} {ι' : Type u'} [Fintype ι'] [DecidableEq ι'] (d : ι → ι' → ℕ) :

    The count matrix of ofCountMat d is d.

    theorem PFunctor.Lens.ofCountMat_countMat {ι : Type u} {ι' : Type u'} [Fintype ι'] [DecidableEq ι'] (g : (purePower ι').bang.Lens (purePower ι)) :
    (ofCountMat fun (i : (purePower ι).B (g.toFunA PUnit.unit)) (j : (purePower ι').B PUnit.unit) => g.countMat PUnit.unit i j) = g

    A one-shape Diller–Nahm morphism is the morphism of its count matrix.

    def PFunctor.Lens.demand {ι : Type u} {ι' : Type u'} (ω : Type w) [NatCast ω] [DecidableEq ι'] (g : (purePower ι').bang.Lens (purePower ι)) :
    ι → ι' → ω

    The demand matrix of a one-shape Diller–Nahm morphism: its count matrix, cast to ω.

    Equations
    Instances For
      theorem PFunctor.Lens.demand_nonneg {ι : Type u} {ι' : Type u'} {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] [DecidableEq ι'] (g : (purePower ι').bang.Lens (purePower ι)) :
      0 ≤ demand ω g

      Demand matrices are nonnegative.

      theorem PFunctor.Lens.demandHom_demand {ι : Type u} {ι' : Type u'} {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] [Fintype ι] [DecidableEq ι'] (g : (purePower ι').bang.Lens (purePower ι)) (u : ι → ω) :
      (demandHom (demand ω g) ⋯) u = Matrix.vecMul u (Matrix.of (demand ω g))

      The demand map of a demand matrix is the vector–matrix product.

      theorem PFunctor.Lens.demand_bangCounit {ι : Type u} {ω : Type w} [CommSemiring ω] [DecidableEq ι] :
      demand ω (bangCounit (purePower ι)) = fun (i : ι) => Pi.single i 1

      The demand matrix of the counit is the identity matrix.

      theorem PFunctor.Lens.demand_bangComp_eq_mul {ι : Type u} {ι' : Type u'} {ι'' : Type u''} {ω : Type w} [CommSemiring ω] [Fintype ι'] [DecidableEq ι'] [DecidableEq ι''] (g : (purePower ι').bang.Lens (purePower ι)) (f : (purePower ι'').bang.Lens (purePower ι')) :

      Composition agrees. The demand matrix of a co-Kleisli composite is the product of the demand matrices.

      theorem PFunctor.Lens.demand_bangComp {ι : Type u} {ι' : Type u'} {ι'' : Type u''} {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] [Fintype ι'] [DecidableEq ι'] [DecidableEq ι''] (g : (purePower ι').bang.Lens (purePower ι)) (f : (purePower ι'').bang.Lens (purePower ι')) :
      demand ω (g.bangComp f) = fun (i : ι) => (demandHom (demand ω f) ⋯) (demand ω g i)

      The demand matrix of a co-Kleisli composite is the composite demand of Handler.isChargeBound_liftM_demand_comp: the demand map of f applied to each row of g.

      Handlers certified by count matrices #

      structure PFunctor.Handler.CountCertified {ι : Type u} {ι' : Type u'} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] (P : PFunctor.{uA, uB}) (Q : PFunctor.{uA₂, uB₂}) (c : P.A → ι → ω) (e : Q.A → ι' → ω) :
      Type (max (max (max (max (max u u') uA) uA₂) uB) uB₂)

      A handler implementing P by programs over Q, certified by a one-shape Diller–Nahm morphism from the resources ι' of Q to the resources ι of P: each call at a is implemented with use vector at most ∑ i, c a i • lens.demand ω i.

      Instances For
        def PFunctor.Handler.CountCertified.toCertified {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA₂, uB₂}} {ι : Type u} {ι' : Type u'} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] {c : P.A → ι → ω} {e : Q.A → ι' → ω} (D : CountCertified P Q c e) :
        Certified P Q c e

        The certified handler with the demand map of the count matrix as its exchange.

        Equations
        Instances For
          @[simp]
          theorem PFunctor.Handler.CountCertified.toCertified_handler {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA₂, uB₂}} {ι : Type u} {ι' : Type u'} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] {c : P.A → ι → ω} {e : Q.A → ι' → ω} (D : CountCertified P Q c e) :
          theorem PFunctor.Handler.CountCertified.toCertified_exchange_apply {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA₂, uB₂}} {ι : Type u} {ι' : Type u'} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] {c : P.A → ι → ω} {e : Q.A → ι' → ω} (D : CountCertified P Q c e) (u : ι → ω) :

          The exchange of a handler certified by a count matrix is the vector–matrix product.

          theorem PFunctor.Handler.CountCertified.isChargeBound_liftM {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA₂, uB₂}} {ι : Type u} {ι' : Type u'} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] {c : P.A → ι → ω} {e : Q.A → ι' → ω} (D : CountCertified P Q c e) {α : Type uB} {x : P.FreeM α} {u : ι → ω} (hx : x.IsChargeBound c u) :

          Use bounds through a handler certified by a count matrix. A program with use vector u runs with use vector u times the demand matrix.

          def PFunctor.Handler.CountCertified.ofNatDemand {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA₂, uB₂}} {ι : Type u} {ι' : Type u'} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] {c : P.A → ι → ω} {e : Q.A → ι' → ω} [Fintype ι'] (h : Handler Q.FreeM P) (d : ι → ι' → ℕ) (hh : ∀ (a : P.A), (h a).IsChargeBound e (∑ i : ι, c a i • fun (j : ι') => ↑(d i j))) :

          A handler certified by a demand map with natural-number entries, certified by the one-shape Diller–Nahm morphism of that matrix.

          Equations
          Instances For
            theorem PFunctor.Handler.CountCertified.countMat_ofNatDemand {P : PFunctor.{uA, uB}} {Q : PFunctor.{uA₂, uB₂}} {ι : Type u} {ι' : Type u'} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] {c : P.A → ι → ω} {e : Q.A → ι' → ω} [Fintype ι'] (h : Handler Q.FreeM P) (d : ι → ι' → ℕ) (hh : ∀ (a : P.A), (h a).IsChargeBound e (∑ i : ι, c a i • fun (j : ι') => ↑(d i j))) :

            The count matrix of ofNatDemand h d hh is d.

            def PFunctor.Handler.CountCertified.id {ι : Type u} [Fintype ι] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [DecidableEq ι] (P : PFunctor.{uA, uB}) (c : P.A → ι → ω) :

            The identity handler, certified by the counit.

            Equations
            Instances For
              theorem PFunctor.Handler.CountCertified.toCertified_id {ι : Type u} [Fintype ι] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] [DecidableEq ι] (P : PFunctor.{uA, uB}) (c : P.A → ι → ω) :

              The identity handler's certificate is the identity certificate.

              def PFunctor.Handler.CountCertified.comp {P : PFunctor.{uA, uB}} {R : PFunctor.{uA₃, uB₃}} {ι : Type u} {ι' : Type u'} {ι'' : Type u''} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] {c : P.A → ι → ω} [Fintype ι'] {f : R.A → ι'' → ω} [DecidableEq ι''] {Q : PFunctor.{uA₂, uB}} {e : Q.A → ι' → ω} (D₂ : CountCertified Q R e f) (D₁ : CountCertified P Q c e) :

              Handlers certified by count matrices compose, with the co-Kleisli composite of their lenses in the opposite order.

              Equations
              Instances For
                theorem PFunctor.Handler.CountCertified.toCertified_comp {P : PFunctor.{uA, uB}} {R : PFunctor.{uA₃, uB₃}} {ι : Type u} {ι' : Type u'} {ι'' : Type u''} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] {c : P.A → ι → ω} [Fintype ι'] {f : R.A → ι'' → ω} [DecidableEq ι''] {Q : PFunctor.{uA₂, uB}} {e : Q.A → ι' → ω} (D₂ : CountCertified Q R e f) (D₁ : CountCertified P Q c e) :

                Composition agrees. The certified handler of a composite is the composite of the certified handlers: composing exchanges of demand maps is the product of count matrices.

                theorem PFunctor.Handler.CountCertified.isChargeBound_liftM_comp {P : PFunctor.{uA, uB}} {R : PFunctor.{uA₃, uB₃}} {ι : Type u} {ι' : Type u'} {ι'' : Type u''} [Fintype ι] [DecidableEq ι'] {ω : Type w} [CommSemiring ω] [PartialOrder ω] [IsOrderedRing ω] {c : P.A → ι → ω} [Fintype ι'] {f : R.A → ι'' → ω} [DecidableEq ι''] {Q : PFunctor.{uA₂, uB}} {e : Q.A → ι' → ω} (D₂ : CountCertified Q R e f) (D₁ : CountCertified P Q c e) {α : Type uB} {x : P.FreeM α} {u : ι → ω} (hx : x.IsChargeBound c u) :

                Use bounds through two handlers. A program with use vector u runs through the composite with use vector u times the product of the two demand matrices.