YukonModule.PolyFun.Control.Comonad.Basic.part0
DefinitionYukon_10831ccd74876e9f55e362e2better-codes
Source module PolyFun.Control.Comonad.Basic.
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 Mathlib.Logic.Equiv.Prod
public import Init
set_option backward.isDefEq.respectTransparency.types false
/-! # Comonads
This file defines the `Comonad` typeclass hierarchy, dual to `Monad`.
It follows the structure of the `Monad` hierarchy:
`Extract` (`pure`), `Extend` (`bind`), `Coseq` (`seq`),
`Coapplicative` (`Applicative`), `Comonad` (`Monad`).
## Hierarchy
* `Extract (w)`: Provides `extract : w α → α`.
* `Extend (w)`: Provides `extend : w α → (w α → β) → w β`.
* `Coseq (w)`: Provides `coseq : w α → w β → w (α × β)` (operator `<@>`).
* `CoseqLeft (w)`: Provides `coseqLeft : w α → w β → w α` (operator `<@`).
* `CoseqRight (w)`: Provides `coseqRight : w α → w β → w β` (operator `@>`).
* `Coapplicative (w)`: Extends `Functor`, `Extract`, `Coseq`, `CoseqLeft`, `CoseqRight`.
* `Comonad (w)`: Extends `Coapplicative`, `Extend`. Provides default `map`.
* `Lawful` variants mirroring `LawfulFunctor`, `LawfulApplicative`, `LawfulMonad`.
-/
@[expose] public section
universe u v z
/-- The `Extract` typeclass provides the `extract` operation, dual to `Pure.pure`. -/
class Extract (w : Type u → Type v) where
/-- Extract a value from the comonadic context. -/
extract {α : Type u} : w α → α
/-- The `Extend` typeclass provides the `extend` operation, dual to `Bind.bind`. -/
class Extend (w : Type u → Type v) where
/-- Extend a function across the comonadic context. -/
extend {α β : Type u} : w α → (w α → β) → w β
/-- The `Coseq` typeclass provides the `coseq` operation (`<@>`), dual to `Seq.seq` (`<*>`).
It combines two comonadic contexts, pairing their results. -/
class Coseq (w : Type u → Type v) where
/-- Combine two comonadic contexts. -/
coseq : {α β : Type u} → w α → w β → w (α × β)
/-- The `CoseqLeft` typeclass provides the `coseqLeft` operation (`<@`), dual to `SeqLeft.seqLeft`
(`<*`). Evaluates two contexts but returns the result of the first. -/
class CoseqLeft (w : Type u → Type v) where
/-- Evaluate two contexts, returning the first result. -/
coseqLeft : {α β : Type u} → w α → w β → w α
/-- The `CoseqRight` typeclass provides the `coseqRight` operation (`@>`), dual to
`SeqRight.seqRight` (`*>`). Evaluates two contexts but returns the result of the second. -/
class CoseqRight (w : Type u → Type v) where
/-- Evaluate two contexts, returning the second result. -/
coseqRight : {α β : Type u} → w α → w β → w β
export Extract (extract)
export Extend (extend)
export Coseq (coseq)
export CoseqLeft (coseqLeft)
export CoseqRight (coseqRight)
/-- Cosequencing `Coseq.coseq`, pairing two comonadic contexts. -/
infixl:60 " <@> " => Coseq.coseq
/-- Left cosequencing `CoseqLeft.coseqLeft`, keeping the left context's result. -/
infixl:60 " <@ " => CoseqLeft.coseqLeft
/-- Right cosequencing `CoseqRight.coseqRight`, keeping the right context's result. -/
infixl:60 " @> " => CoseqRight.coseqRight
/-- `Coapplicative` functor. Dual to `Applicative`.
Combines `Functor`, `Extract`, and `Coseq` operations. -/
class Coapplicative (w : Type u → Type v) extends
Functor w, Extract w, Coseq w, CoseqLeft w, CoseqRight w where
/-- Default implementation for `coseqLeft` using `coseq` and `map`. -/
coseqLeft wa wb := Functor.map Prod.fst (coseq wa wb)
/-- Default implementation for `coseqRight` using `coseq` and `map`. -/
coseqRight wa wb := Functor.map Prod.snd (coseq wa wb)
/-- `Comonad`. Dual to `Monad`.
Combines `Coapplicative` structure with `Extend`. -/
class Comonad (w : Type u → Type v) extends Coapplicative w, Extend w where
/-- Default implementation for `map` using `extend` and `extract`.
Note: This requires that the `Functor` instance provided to `Coapplicative`
is compatible with this definition. `LawfulComonad` ensures this. -/
map f wa := extend wa (f ∘ extract)
/-- Default `coseq` built only from `extend` and `extract`.
For two contexts `wa : w α`, `wb : w β` we:
1. `extend` over the first context, so we may look inside it,
2. pair its extracted value with the *already* extracted value of `wb`.
This yields `w (α × β)` as required. -/
coseq wa wb := extend wa (fun wa' => (extract wa', extract wb))
/-! ## Lawful hierarchy -/
/-- Lawful `Coapplicative` functor. Dual to `LawfulApplicative`. -/
class LawfulCoapplicative (w : Type u → Type v) [Coapplicative w] extends LawfulFunctor w where
/-- Ensure default `coseqLeft` law holds even if overridden. -/
coseqLeft_eq : ∀ {α β : Type u} (wa : w α) (wb : w β),
@coseqLeft w _ α β wa wb = Functor.map (@Prod.fst α β) (coseq wa wb)
/-- Ensure default `coseqRight` law holds even if overridden. -/
coseqRight_eq : ∀ {α β : Type u} (wa : w α) (wb : w β),
coseqRight wa wb = Functor.map (@Prod.snd α β) (coseq wa wb)
/-- Associativity law for `coseq`. `assoc` maps `(α × β) × γ` to `α × (β × γ)`. -/
coseq_assoc : ∀ {α β γ : Type u} (wa : w α) (wb : w β) (wc : w γ),
Functor.map (Equiv.prodAssoc α β γ) (coseq (coseq wa wb) wc) = coseq wa (coseq wb wc)
/-- Naturality of `coseq` in both arguments. -/
map_coseq : ∀ {α β α' β' : Type u} (f : α → α') (g : β → β')
(wa : w α) (wb : w β),
Functor.map (fun p : α × β => (f p.1, g p.2)) (coseq wa wb) =
coseq (Functor.map f wa) (Functor.map g wb)
-- Other potential laws like extract_coseq : extract (wa <@> wb) = (extract wa, extract wb)
-- are often added but require `w (α × β)` structure, so omitted here for generality.
export LawfulCoapplicative (coseqLeft_eq coseqRight_eq coseq_assoc map_coseq)
/-- Lawful `Comonad`. Dual to `LawfulMonad`. -/
class LawfulComonad (w : Type u → Type v) [Comonad w] extends LawfulCoapplicative w where
/-- Compatibility between `map` and `extend`/`extract`.
Since `Comonad.map` defines map this way, this law ensures the `Functor` instance
used by `LawfulCoapplicative` (and `LawfulFunctor`) is consistent. -/
map_eq_extend_extract : ∀ {α β : Type u} (f : α → β) (wa : w α),
Functor.map f wa = extend wa (f ∘ extract)
/-- Extending with `extract` is the identity (Left identity dual). -/
extend_extract : ∀ {α : Type u} (wa : w α), extend wa (@extract w _ α) = wa
/-- Extracting after extending yields the original function application (Right identity dual). -/
extract_extend : ∀ {α β : Type u} (wa : w α) (f : w α → β),
extract (extend wa f) = f wa
/-- Extend is associative (Associativity dual). -/
extend_assoc : ∀ {α β γ : Type u} (wa : w α) (f : w α → β) (g : w β → γ),
extend (extend wa f) g = extend wa (fun w'a => g (extend w'a f))
export LawfulComonad (map_eq_extend_extract extend_extract extract_extend extend_assoc)
/-! ## Theorems derived from lawful classes -/
section LawfulnessProofs
variable {w : Type u → Type v} [Comonad w] [LawfulComonad w]
theorem comonad_id_map {α : Type u} (wa : w α) : Functor.map id wa = wa :=
id_map wa
@[simp] theorem comonad_comp_map {α β γ : Type u} (f : β → γ) (g : α → β) (wa : w α) :
Functor.map (f ∘ g) wa = Functor.map f (Functor.map g wa) :=
comp_map g f wa
@[simp] theorem extract_map {α β : Type u} (f : α → β) (wa : w α) :
extract (Functor.map f wa) = f (extract wa) := by
rw [map_eq_extend_extract, extract_extend, Function.comp_apply]
end LawfulnessProofs
/-! ## Duplicate and derived laws
These require `w : Type u → Type u`, so the comonadic context can be nested. -/
section Duplicate
variable {w : Type u → Type u} [Comonad w]
/-- Duplicate the comonadic context. Defined via `extend`. -/
@[simp]
def duplicate {α : Type u} (wa : w α) : w (w α) :=
extend wa id
variable [LawfulComonad w]
variable {α : Type u} (wa : w α)
theorem extract_duplicate_eq_id : extract (duplicate wa) = wa :=
extract_extend wa id
theorem map_extract_duplicate_eq_id : Functor.map extract (duplicate wa) = wa := by
rw [duplicate, map_eq_extend_extract, extend_assoc]
simp only [Function.comp_apply, extract_extend, id_def]
rw [extend_extract]
theorem extend_eq_map_duplicate {β : Type u} (f : w α → β) :
extend wa f = Functor.map f (duplicate wa) := by
rw [duplicate, map_eq_extend_extract, extend_assoc]
simp only [Function.comp_apply, extract_extend, id_def]
theorem duplicate_duplicate_eq_map_duplicate :
duplicate (duplicate wa) = Functor.map duplicate (duplicate wa) := by
have h_lhs : duplicate (duplicate wa) = extend wa duplicate := by
rw [duplicate, duplicate, extend_assoc]
simp only [id_def]
rfl
have h_rhs : Functor.map duplicate (duplicate wa) = extend wa duplicate := by
rw [duplicate, map_eq_extend_extract, extend_assoc]
simp only [Function.comp_apply, extract_extend, id_def]
rw [h_lhs, h_rhs]
end Duplicate
Source