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.obj α 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 (n + 1)) : PFunctor.M (MvPFunctor.last P) → Fin2 n → Type u

• root: {n : ℕ} → {P : MvPFunctor (n + 1)} → (x : PFunctor.M (MvPFunctor.last P)) → (a : P.A) → (f : PFunctor.B (MvPFunctor.last P) a → PFunctor.M (MvPFunctor.last P)) → PFunctor.M.dest x = { fst := a, snd := f } → (i : Fin2 n) → MvPFunctor.B (MvPFunctor.drop P) a i → MvPFunctor.M.Path P x i
• child: {n : ℕ} → {P : MvPFunctor (n + 1)} → (x : PFunctor.M (MvPFunctor.last P)) → (a : P.A) → (f : PFunctor.B (MvPFunctor.last P) a → PFunctor.M (MvPFunctor.last P)) → PFunctor.M.dest x = { fst := a, snd := f } → (j : PFunctor.B (MvPFunctor.last P) a) → (i : Fin2 n) → MvPFunctor.M.Path P (f j) i → MvPFunctor.M.Path P x i

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

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

def MvPFunctor.mp {n : ℕ} (P : MvPFunctor (n + 1)) : MvPFunctor 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.Obj α is made of a tree and a function from its valid paths to the values it contains

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

n-ary M-type for P

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

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

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

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

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

Proof of type equality as an arrow

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

Proof of type equality as a function

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

Using corecursion, construct the contents of an M-type

Equations

• One or more equations did not get rendered due to their size.
• MvPFunctor.M.corecContents P g₀ g₁ g₂ x b h x (MvPFunctor.M.Path.root x a f h' x c) = let_fun this := (_ : a = g₀ b); g₁ b x (MvPFunctor.castDropB P this x c)

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

Corecursor for M-type of P

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

Corecursor for M-type of P

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

Implementation of destructor for M-type of P

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

Implementation of destructor for M-type of P

def MvPFunctor.M.dest' {n : ℕ} (P : MvPFunctor (n + 1)) {α : TypeVec n} {x : PFunctor.M (MvPFunctor.last P)} {a : P.A} {f : PFunctor.B (MvPFunctor.last P) a → PFunctor.M (MvPFunctor.last P)} (h : PFunctor.M.dest x = { fst := a, snd := f }) (f' : TypeVec.Arrow (MvPFunctor.M.Path P x) α) : MvPFunctor.Obj P (α ::: MvPFunctor.M P α)

Destructor for M-type of P

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

Destructor for M-types

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

Constructor for M-types

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

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

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

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

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

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

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

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

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

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