Documentation

PolyFun.IPFunctor.Scoped.Size

Description size of finitely branching scoped terms #

Count every variable and operation once. Bound syntax bodies are counted as stored descriptions, independently of how often an interpretation executes them. This is a syntax measure, not a bound on evaluation time or output size.

def IPFunctor.ScopedSignature.Term.nodeCount {S : Type u} {σ : ScopedSignature S} [{a : S} → (op : σ.Op a) → Fintype (σ.Arg op)] {Γ : List S} {a : S} (t : σ.Term Γ a) :

Number of variables and constructor occurrences in a finite-branching term.

Equations
  • One or more equations did not get rendered due to their size.
Instances For
    @[simp]
    theorem IPFunctor.ScopedSignature.Term.nodeCount_var {S : Type u} {σ : ScopedSignature S} [{a : S} → (op : σ.Op a) → Fintype (σ.Arg op)] {Γ : List S} {a : S} (x : ScopedVar Γ a) :
    @[simp]
    theorem IPFunctor.ScopedSignature.Term.nodeCount_node {S : Type u} {σ : ScopedSignature S} [{a : S} → (op : σ.Op a) → Fintype (σ.Arg op)] {Γ : List S} {a : S} (op : σ.Op a) (args : (p : σ.Arg op) → σ.Term (σ.binders op p ++ Γ) (σ.sort op p)) :
    (node op args).nodeCount = 1 + ∑ p : σ.Arg op, (args p).nodeCount