YukonModule.PolyFun.PFunctor.Cofree.part0
DefinitionYukon_58df3d63414aa63c49ca2793better-codes
Source module PolyFun.PFunctor.Cofree.
Definition code
/-
Copyright (c) 2026 PolyFun Contributors. All rights reserved.
Released under Apache 2.0 license as described in the file LICENSE.
Authors: Quang Dao
-/
module
public import Definitions.Def_Yukon_10831ccd74876e9f55e362e2
public import Mathlib.Data.PFunctor.Univariate.M
public import Definitions.Def_Yukon_e97603cba4eb54e3bbc4768a
public import Mathlib.Data.PFunctor.Multivariate.Basic
public import Init
public import Mathlib.Logic.Equiv.Prod
meta import Definitions.Def_Yukon_10831ccd74876e9f55e362e2
meta import Definitions.Def_Yukon_e97603cba4eb54e3bbc4768a
set_option backward.isDefEq.respectTransparency.types false
/-! # Cofree Comonads
This file defines the `Cofree` comonad, which is a comonad that is constructed from a functor and a
coalgebra.
Since this is a coinductive type, the only way to define it right now is to use the `M` type
construction from `PFunctor`.
## Main definitions
* `PFunctor.CofreeC`: The `Cofree` comonad.
-/
@[expose] public section
universe uA uB u v
namespace PFunctor
/-- `constProd F α` is the polynomial functor `X ↦ α × F X`. It is the key ingredient of the cofree
comonad on `F`.
This is equivalent to `C α * F` but without a `⊕ PEmpty` in the children type. -/
def constProd (P : PFunctor.{uA, uB}) (α : Type u) : PFunctor.{max uA u, uB} where
A := α × P.A
B := fun s : α × P.A => P.B s.2
/-- `CofreeC F α` is the cofree comonad generated by `F`
with head labels of type `α`. -/
def CofreeC (F : PFunctor.{uA, uB}) (α : Type u) : Type _ :=
M.{max uA u, uB} (constProd F α)
namespace CofreeC
variable {F : PFunctor.{uA, uB}} {α : Type u}
/-- Head (label) of a cofree tree. -/
def head (t : CofreeC F α) : α :=
(M.dest t).1.1
/-- Tail of a cofree tree (an `F`-structured family of sub-trees). -/
def tail (t : CofreeC F α) : F (CofreeC F α) :=
let d := M.dest t -- d : constProd F α (CofreeC F α)
⟨d.1.2, d.2⟩ -- drop the constant `α` stored in `d.1.1`
/-- Comonad counit: extract the label at the root of a cofree tree, i.e. its `head`. -/
def extract (t : CofreeC F α) : α :=
head t
/-- One-step coalgebra map for `extend`: relabel the root of `t` by `f t` while
keeping the `F`-structured family of sub-trees. -/
def extendF {β : Type u} (f : CofreeC F α → β) (t : CofreeC F α) :
constProd F β (CofreeC F α) :=
let d := M.dest t
⟨(f t, d.1.2), d.2⟩
/-- Comonad coextension: relabel every node of `t` by applying `f` to the sub-tree
rooted at that node. -/
def extend {β : Type u} (t : CofreeC F α) (f : CofreeC F α → β) : CofreeC F β :=
M.corec (extendF f) t
@[simp] theorem extendF_extract (t : CofreeC F α) : extendF extract t = M.dest t := by
induction t using PFunctor.M.casesOn' with
| _ a g =>
cases a
simp only [extendF, extract, head, M.dest_mk]
rfl
@[simp] theorem dest_extend {β : Type u} (t : CofreeC F α) (f : CofreeC F α → β) :
M.dest (extend t f) = (constProd F β).map (fun x => extend x f) (extendF f t) := by
simp only [extend]; exact M.dest_corec (P := constProd F β) (g := extendF f) t
theorem dest_extend_eq {β : Type u} (t : CofreeC F α) (f : CofreeC F α → β) :
M.dest (extend t f) = ⟨(f t, (M.dest t).1.2), (fun x => extend x f) ∘ (M.dest t).2⟩ := by
simp only [dest_extend, extendF, PFunctor.map_eq]
rfl
@[simp] theorem head_extend {β : Type u} (t : CofreeC F α) (f : CofreeC F α → β) :
head (extend t f) = f t := by
simp [head, extendF, PFunctor.map_eq]
@[simp] theorem tail_extend {β : Type u} (t : CofreeC F α) (f : CofreeC F α → β) :
tail (extend t f) = F.map (fun x => extend x f) (tail t) := by
unfold tail
rw [dest_extend]
simp only [extendF, PFunctor.map_eq]
rfl
instance _root_.PFunctor.CofreeC.instComonad : Comonad (CofreeC F) where
extract := extract
extend := extend
@[simp] theorem extend_extract (t : CofreeC F α) : extend t extract = t := by
let h : CofreeC F α → CofreeC F α := fun x => extend x extract
have h_corec : h = M.corec (F := constProd F α) M.dest := by
apply M.corec_unique (P := constProd F α) (g := M.dest) (f := h)
intro x
simp only [dest_extend, extendF_extract, h]
rfl
have hid_corec : (id : CofreeC F α → CofreeC F α) = M.corec (F := constProd F α) M.dest := by
apply M.corec_unique (P := constProd F α) (g := M.dest) (f := id)
intro x
simp [PFunctor.id_map (P := constProd F α) (x := M.dest x)]
have h_eq_id : h = id := by rw [h_corec, hid_corec]
simpa [h] using congrArg (fun k => k t) h_eq_id
@[simp] theorem extract_extend {β : Type u} (t : CofreeC F α) (f : CofreeC F α → β) :
extract (extend t f) = f t := by
simp [extract]
@[simp] theorem extend_assoc {β γ : Type u} (t : CofreeC F α) (f : CofreeC F α → β)
(g : CofreeC F β → γ) :
extend (extend t f) g = extend t (fun x => g (extend x f)) := by
let l : CofreeC F α → CofreeC F γ := fun x => extend (extend x f) g
let r : CofreeC F α → CofreeC F γ := fun x => extend x (fun y => g (extend y f))
have hr_corec : r = M.corec (F := constProd F γ) (extendF (fun y => g (extend y f))) := rfl
have hl_corec : l = M.corec (F := constProd F γ) (extendF (fun y => g (extend y f))) := by
apply M.corec_unique (P := constProd F γ)
(g := extendF (fun y => g (extend y f))) (f := l)
intro x
change M.dest (extend (extend x f) g) =
(constProd F γ).map l (extendF (fun y => g (extend y f)) x)
rw [dest_extend_eq]
have hdest : M.dest (extend x f) =
⟨(f x, (M.dest x).1.2), (fun y => extend y f) ∘ (M.dest x).2⟩ := dest_extend_eq x f
rw [hdest]
have hfun :
(fun x => extend x g) ∘ (fun y => extend y f) ∘ (M.dest x).2 =
(fun x => extend (extend x f) g) ∘ (M.dest x).2 := by
funext i
rfl
cases hfun
rfl
have hl_eq_r : l = r := by rw [hl_corec, hr_corec]
simpa [l, r] using congrArg (fun k => k t) hl_eq_r
instance _root_.PFunctor.CofreeC.instLawfulComonad : LawfulComonad (CofreeC F) where
map_const := rfl
id_map := by
intro α t
simp [Functor.map]
comp_map := by
intro α β γ f g t
change extend t ((g ∘ f) ∘ extract) = extend (extend t (f ∘ extract)) (g ∘ extract)
rw [extend_assoc]
congr 1
coseqLeft_eq := by
intro α β wa wb
rfl
coseqRight_eq := by
intro α β wa wb
rfl
coseq_assoc := by
intro α β γ wa wb wc
simp [coseq, Functor.map, Function.comp, extend_assoc]
map_coseq := by
intro α β α' β' f g wa wb
simp [coseq, Functor.map, Function.comp, extend_assoc]
map_eq_extend_extract := by
intro α β f t
rfl
extend_extract := by
intro α t
exact CofreeC.extend_extract t
extract_extend := by
intro α β t f
exact CofreeC.extract_extend t f
extend_assoc := by
intro α β γ t f g
exact CofreeC.extend_assoc t f g
end CofreeC
end PFunctor
Source