The M construction as a multivariate polynomial functor.

M types are potentially infinite tree-like structures. They are defined as the greatest fixpoint of a polynomial functor.

Main definitions

• M.mk - constructor
• M.dest - destructor
• M.corec - corecursor: useful for formulating infinite, productive computations
• M.bisim - bisimulation: proof technique to show the equality of infinite objects

Implementation notes

Dual view of M-types:

• mp: polynomial functor
• M: greatest fixed point of a polynomial functor

Specifically, we define the polynomial functor mp as:

• A := a possibly infinite tree-like structure without information in the nodes
• B := given the tree-like structure t, B t is a valid path from the root of t to any given node.

As a result mp α is made of a dataless tree and a function from its valid paths to values of α

The difference with the polynomial functor of an initial algebra is that A is a possibly infinite tree.

Reference

• Jeremy Avigad, Mario M. Carneiro and Simon Hudon. [Data Types as Quotients of Polynomial Functors][avigad-carneiro-hudon2019]

inductive MvPFunctor.M.Path {n : ℕ} (P : MvPFunctor.{u} (n + 1)) : P.last.M → Fin2 n → Type u

A path from the root of a tree to one of its node

• root {n : ℕ} {P : MvPFunctor.{u} (n + 1)} (x : P.last.M) (a : P.A) (f : P.last.B a → P.last.M) (h : x.dest = ⟨a, f⟩) (i : Fin2 n) (c : P.drop.B a i) : Path P x i
• child {n : ℕ} {P : MvPFunctor.{u} (n + 1)} (x : P.last.M) (a : P.A) (f : P.last.B a → P.last.M) (h : x.dest = ⟨a, f⟩) (j : P.last.B a) (i : Fin2 n) (c : Path P (f j) i) : Path P x i

instance MvPFunctor.M.Path.inhabited {n : ℕ} (P : MvPFunctor.{u} (n + 1)) (x : P.last.M) {i : Fin2 n} [Inhabited (P.drop.B x.head i)] : Inhabited (Path P x i)

Equations

• MvPFunctor.M.Path.inhabited P x = { default := MvPFunctor.M.Path.root x x.head x.children ⋯ i default }

def MvPFunctor.mp {n : ℕ} (P : MvPFunctor.{u} (n + 1)) : MvPFunctor.{u} n

Polynomial functor of the M-type of P. A is a data-less possibly infinite tree whereas, for a given a : A, B a is a valid path in tree a so that mp α is made of a tree and a function from its valid paths to the values it contains

Equations

• P.mp = { A := P.last.M, B := MvPFunctor.M.Path P }

def MvPFunctor.M {n : ℕ} (P : MvPFunctor.{u} (n + 1)) (α : TypeVec.{u} n) : Type u

n-ary M-type for P

Equations

• P.M α = ↑P.mp α

instance MvPFunctor.mvfunctorM {n : ℕ} (P : MvPFunctor.{u} (n + 1)) : MvFunctor P.M

Equations

• P.mvfunctorM = id inferInstance

instance MvPFunctor.inhabitedM {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} [I : Inhabited P.A] [(i : Fin2 n) → Inhabited (α i)] : Inhabited (P.M α)

Equations

• P.inhabitedM = MvPFunctor.Obj.inhabited P.mp

def MvPFunctor.M.corecShape {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {β : Type u} (g₀ : β → P.A) (g₂ : (b : β) → P.last.B (g₀ b) → β) : β → P.last.M

construct through corecursion the shape of an M-type without its contents

Equations

• MvPFunctor.M.corecShape P g₀ g₂ = PFunctor.M.corec fun (b : β) => ⟨g₀ b, g₂ b⟩

def MvPFunctor.castDropB {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {a a' : P.A} (h : a = a') : (P.drop.B a).Arrow (P.drop.B a')

Proof of type equality as an arrow

Equations

• P.castDropB h _i b = Eq.recOn h b

def MvPFunctor.castLastB {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {a a' : P.A} (h : a = a') : P.last.B a → P.last.B a'

Proof of type equality as a function

Equations

• P.castLastB h b = Eq.recOn h b

def MvPFunctor.M.corecContents {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {β : Type u} (g₀ : β → P.A) (g₁ : (b : β) → (P.drop.B (g₀ b)).Arrow α) (g₂ : (b : β) → P.last.B (g₀ b) → β) (x : P.last.M) (b : β) (h : x = corecShape P g₀ g₂ b) : TypeVec.Arrow (Path P x) α

Using corecursion, construct the contents of an M-type

Equations

• MvPFunctor.M.corecContents P g₀ g₁ g₂ x b h x✝ (MvPFunctor.M.Path.root x a f h' x✝ c) = g₁ b x✝ (P.castDropB ⋯ x✝ c)
• MvPFunctor.M.corecContents P g₀ g₁ g₂ x b h x✝ (MvPFunctor.M.Path.child x a f h' j x✝ c) = MvPFunctor.M.corecContents P g₀ g₁ g₂ (f j) (g₂ b (P.castLastB ⋯ j)) ⋯ x✝ c

def MvPFunctor.M.corec' {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {β : Type u} (g₀ : β → P.A) (g₁ : (b : β) → (P.drop.B (g₀ b)).Arrow α) (g₂ : (b : β) → P.last.B (g₀ b) → β) : β → P.M α

Corecursor for M-type of P

Equations

• MvPFunctor.M.corec' P g₀ g₁ g₂ b = ⟨MvPFunctor.M.corecShape P g₀ g₂ b, MvPFunctor.M.corecContents P g₀ g₁ g₂ (MvPFunctor.M.corecShape P g₀ g₂ b) b ⋯⟩

def MvPFunctor.M.corec {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {β : Type u} (g : β → ↑P (α ::: β)) : β → P.M α

Corecursor for M-type of P

Equations

• MvPFunctor.M.corec P g = MvPFunctor.M.corec' P (fun (b : β) => (g b).fst) (fun (b : β) => TypeVec.dropFun (g b).snd) fun (b : β) => TypeVec.lastFun (g b).snd

def MvPFunctor.M.pathDestLeft {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u_1} n} {x : P.last.M} {a : P.A} {f : P.last.B a → P.last.M} (h : x.dest = ⟨a, f⟩) (f' : TypeVec.Arrow (Path P x) α) : (P.drop.B a).Arrow α

Implementation of destructor for M-type of P

Equations

• MvPFunctor.M.pathDestLeft P h f' i c = f' i (MvPFunctor.M.Path.root x a f h i c)

def MvPFunctor.M.pathDestRight {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u_1} n} {x : P.last.M} {a : P.A} {f : P.last.B a → P.last.M} (h : x.dest = ⟨a, f⟩) (f' : TypeVec.Arrow (Path P x) α) (j : P.last.B a) : TypeVec.Arrow (Path P (f j)) α

Implementation of destructor for M-type of P

Equations

• MvPFunctor.M.pathDestRight P h f' j i c = f' i (MvPFunctor.M.Path.child x a f h j i c)

def MvPFunctor.M.dest' {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {x : P.last.M} {a : P.A} {f : P.last.B a → P.last.M} (h : x.dest = ⟨a, f⟩) (f' : TypeVec.Arrow (Path P x) α) : ↑P (α ::: P.M α)

Destructor for M-type of P

Equations

• MvPFunctor.M.dest' P h f' = ⟨a, TypeVec.splitFun (MvPFunctor.M.pathDestLeft P h f') fun (x_1 : (P.B a).last) => ⟨f x_1, MvPFunctor.M.pathDestRight P h f' x_1⟩⟩

def MvPFunctor.M.dest {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} (x : P.M α) : ↑P (α ::: P.M α)

Destructor for M-types

Equations

• MvPFunctor.M.dest P x = MvPFunctor.M.dest' P ⋯ x.snd

def MvPFunctor.M.mk {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} : ↑P (α ::: P.M α) → P.M α

Constructor for M-types

Equations

• MvPFunctor.M.mk P = MvPFunctor.M.corec P fun (i : ↑P (α ::: P.M α)) => MvFunctor.map (TypeVec.id ::: MvPFunctor.M.dest P) i

theorem MvPFunctor.M.dest'_eq_dest' {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {x : P.last.M} {a₁ : P.A} {f₁ : P.last.B a₁ → P.last.M} (h₁ : x.dest = ⟨a₁, f₁⟩) {a₂ : P.A} {f₂ : P.last.B a₂ → P.last.M} (h₂ : x.dest = ⟨a₂, f₂⟩) (f' : TypeVec.Arrow (Path P x) α) : dest' P h₁ f' = dest' P h₂ f'

theorem MvPFunctor.M.dest_eq_dest' {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {x : P.last.M} {a : P.A} {f : P.last.B a → P.last.M} (h : x.dest = ⟨a, f⟩) (f' : TypeVec.Arrow (Path P x) α) : dest P ⟨x, f'⟩ = dest' P h f'

theorem MvPFunctor.M.dest_corec' {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {β : Type u} (g₀ : β → P.A) (g₁ : (b : β) → (P.drop.B (g₀ b)).Arrow α) (g₂ : (b : β) → P.last.B (g₀ b) → β) (x : β) : dest P (corec' P g₀ g₁ g₂ x) = ⟨g₀ x, TypeVec.splitFun (g₁ x) (corec' P g₀ g₁ g₂ ∘ g₂ x)⟩

theorem MvPFunctor.M.dest_corec {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {β : Type u} (g : β → ↑P (α ::: β)) (x : β) : dest P (corec P g x) = MvFunctor.map (TypeVec.id ::: corec P g) (g x)

theorem MvPFunctor.M.bisim_lemma {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} {a₁ : P.mp.A} {f₁ : (P.mp.B a₁).Arrow α} {a' : P.A} {f' : (P.B a').drop.Arrow α} {f₁' : (P.B a').last → P.M α} (e₁ : dest P ⟨a₁, f₁⟩ = ⟨a', TypeVec.splitFun f' f₁'⟩) : ∃ (g₁' : P.last.B a' → P.last.M) (e₁' : PFunctor.M.dest a₁ = ⟨a', g₁'⟩), f' = pathDestLeft P e₁' f₁ ∧ f₁' = fun (x : P.last.B a') => ⟨g₁' x, pathDestRight P e₁' f₁ x⟩

theorem MvPFunctor.M.bisim {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} (R : P.M α → P.M α → Prop) (h : ∀ (x y : P.M α), R x y → ∃ (a : P.A) (f : (P.B a).drop.Arrow (α ::: P.M α).drop) (f₁ : (P.B a).last → (α ::: P.M α).last) (f₂ : (P.B a).last → (α ::: P.M α).last), dest P x = ⟨a, TypeVec.splitFun f f₁⟩ ∧ dest P y = ⟨a, TypeVec.splitFun f f₂⟩ ∧ ∀ (i : (P.B a).last), R (f₁ i) (f₂ i)) (x y : P.M α) (r : R x y) : x = y

theorem MvPFunctor.M.bisim₀ {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} (R : P.M α → P.M α → Prop) (h₀ : Equivalence R) (h : ∀ (x y : P.M α), R x y → MvFunctor.map (TypeVec.id ::: Quot.mk R) (dest P x) = MvFunctor.map (TypeVec.id ::: Quot.mk R) (dest P y)) (x y : P.M α) (r : R x y) : x = y

theorem MvPFunctor.M.bisim' {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α : TypeVec.{u} n} (R : P.M α → P.M α → Prop) (h : ∀ (x y : P.M α), R x y → MvFunctor.map (TypeVec.id ::: Quot.mk R) (dest P x) = MvFunctor.map (TypeVec.id ::: Quot.mk R) (dest P y)) (x y : P.M α) (r : R x y) : x = y

theorem MvPFunctor.M.dest_map {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α β : TypeVec.{u} n} (g : α.Arrow β) (x : P.M α) : dest P (MvFunctor.map g x) = MvFunctor.map (g ::: fun (x : P.M α) => MvFunctor.map g x) (dest P x)

theorem MvPFunctor.M.map_dest {n : ℕ} (P : MvPFunctor.{u} (n + 1)) {α β : TypeVec.{u} n} (g : (α ::: P.M α).Arrow (β ::: P.M β)) (x : P.M α) (h : ∀ (x : P.M α), TypeVec.lastFun g x = MvFunctor.map (TypeVec.dropFun g) x) : MvFunctor.map g (dest P x) = dest P (MvFunctor.map (TypeVec.dropFun g) x)