Martin Escardo, Paulo Oliva, 2023 - 2024
(Strong, wild) universe-polymorphic monads on types.
We use ā : Universe ā Universe to control the functor part. E.g. for
the powerset monad, as the powerset of a type in š¤ lands in the next
universe š¤āŗ, we take ā š¤ = š¤āŗ, but for the list monad we take
ā š¤ = š¤. For the J and K monads with answer type R : š¦,
we have ā š¤ = š¤ ā š¦.
\begin{code}
{-# OPTIONS --safe --without-K #-}
open import MLTT.Spartan
open import UF.Equiv
open import UF.FunExt
\end{code}
In the following definition, it works to make ā into a field, but this
requires the pragma --no-level-universe, which we don't want to
use. In fact, our code originally did have ā as a field, using that
pragma.
\begin{code}
module MonadOnTypes.Definition where
record Monad {ā : Universe ā Universe} : š¤Ļ where
constructor
monad
field
functor : {š¤ : Universe} ā š¤ Ģ ā ā š¤ Ģ
private
T = functor
field
Ī· : {š¤ : Universe} {X : š¤ Ģ } ā X ā T X
ext : {š¤ š„ : Universe} {X : š¤ Ģ } {Y : š„ Ģ } ā (X ā T Y) ā T X ā T Y
ext-Ī· : {š¤ : Universe} {X : š¤ Ģ } ā ext (Ī· {š¤} {X}) ā¼ šš (T X)
unit : {š¤ š„ : Universe} {X : š¤ Ģ } {Y : š„ Ģ } (f : X ā T Y) (x : X)
ā ext f (Ī· x) ļ¼ f x
assoc : {š¤ š„ š¦ : Universe}
{X : š¤ Ģ } {Y : š„ Ģ } {Z : š¦ Ģ }
(g : Y ā T Z) (f : X ā T Y) (t : T X)
ā ext (Ī» x ā ext g (f x)) t ļ¼ ext g (ext f t)
map : {X : š¤ Ģ } {Y : š„ Ģ } ā (X ā Y) ā T X ā T Y
map f = ext (Ī· ā f)
map-id : {X : š¤ Ģ } ā map (šš X) ā¼ šš (T X)
map-id = ext-Ī·
map-ā : Fun-Ext
ā {X : š¤ Ģ } {Y : š„ Ģ } {Z : š¦ Ģ }
(f : X ā Y) (g : Y ā Z)
ā map (g ā f) ā¼ map g ā map f
map-ā fe f g t =
map (g ā f) t ļ¼āØreflā©
ext (Ī» x ā Ī· (g (f x))) t ļ¼āØ by-unit ā©
ext (Ī» x ā ext (Ī» y ā Ī· (g y)) (Ī· (f x))) t ļ¼āØ by-assoc ā©
ext (Ī» x ā Ī· (g x)) (ext (Ī» x ā Ī· (f x)) t) ļ¼āØreflā©
(map g ā map f) t ā
where
by-unit = ap (Ī» - ā ext - t)
(dfunext fe (Ī» x ā (unit (Ī» y ā Ī· (g y)) (f x))ā»Ā¹))
by-assoc = assoc (Ī» x ā Ī· (g x)) (Ī» x ā Ī· (f x)) t
map-āā : Fun-Ext
ā {X : š¤ Ģ } {Y : š„ Ģ } {Z : š¦ Ģ } {T : š£ Ģ }
(f : X ā Y) (g : Y ā Z) (h : Z ā T)
ā map (h ā g ā f) ā¼ map h ā map g ā map f
map-āā fe f g h t =
map (h ā g ā f) t ļ¼āØ by-Tiality ā©
(map (h ā g) ā map f) t ļ¼āØ again-by-functoriality ā©
(map h ā map g) (map f t) ļ¼āØreflā©
(map h ā map g ā map f) t ā
where
by-Tiality = map-ā fe f (h ā g) t
again-by-functoriality = ap (Ī» - ā (- ā map f) t) (dfunext fe (map-ā fe g h))
μ : {X : š¤ Ģ } ā T (T X) ā T X
μ = ext id
ext-is-μ-map : Fun-Ext
ā {X : š¤ Ģ } {Y : š„ Ģ }
(f : X ā T Y)
ā ext f ⼠μ ā map f
ext-is-μ-map fe f tt =
ext f tt ļ¼āØ by-unit ā»Ā¹ ā©
ext (ext id ā Ī· ā f) tt ļ¼āØ by-assoc ā©
(ext id ā ext (Ī· ā f)) tt ļ¼āØreflā©
(μ ā map f) tt ā
where
by-unit = ap (Ī» - ā ext (- ā f) tt) (dfunext fe (unit id))
by-assoc = assoc id (Ī· ā f) tt
μ-assoc : Fun-Ext
ā {X : š¤ Ģ }
ā μ {š¤} {X} ā map (μ {š¤} {X}) ⼠μ {š¤} {X} ā μ {ā š¤} {T X}
μ-assoc fe ttt =
(μ ā map μ) ttt ļ¼āØ (ext-is-μ-map fe μ ttt)ā»Ā¹ ā©
ext μ ttt ļ¼āØreflā©
ext (ext id ā id) ttt ļ¼āØ assoc id id ttt ā©
ext id (ext id ttt) ļ¼āØreflā©
(μ ā μ) ttt ā
Ī·-natural : {X : š¤ Ģ } {Y : š„ Ģ }
(h : X ā Y)
ā map h ā Ī· {š¤} {X} ā¼ Ī· {š„} {Y} ā h
Ī·-natural h x =
map h (Ī· x) ļ¼āØreflā©
ext (Ī» x ā Ī· (h x)) (Ī· x) ļ¼āØ unit (Ī» x ā Ī· (h x)) x ā©
Ī· (h x) ā
μ-natural : Fun-Ext
ā {X : š¤ Ģ } {Y : š„ Ģ }
(h : X ā Y)
ā map h ā μ {š¤} {X} ⼠μ {š„} {Y} ā map (map h)
μ-natural fe h tt =
(map h ā μ) tt ļ¼āØreflā©
ext (Ī· ā h) (ext id tt) ļ¼āØ by-assoc ā»Ā¹ ā©
ext (ext (Ī· ā h)) tt ļ¼āØ by-unit ā»Ā¹ ā©
ext (Ī» t ā ext id (Ī· (ext (Ī· ā h) t))) tt ļ¼āØ again-by-assoc ā©
ext id (ext (Ī» t ā Ī· (ext (Ī· ā h) t)) tt) ļ¼āØreflā©
(μ ā map (map h)) tt ā
where
by-assoc = assoc (Ī» x ā Ī· (h x)) id tt
by-unit = ap (Ī» - ā ext - tt)
(dfunext fe (Ī» t ā unit id (ext (Ī· ā h) t)))
again-by-assoc = assoc id (Ī» x ā Ī· (ext (Ī· ā h) x)) tt
Ī·-unitā : {X : š¤ Ģ } ā μ {š¤} {X} ā Ī· {ā š¤} {T X} ā¼ id
Ī·-unitā t = μ (Ī· t) ļ¼āØreflā©
ext id (Ī· t) ļ¼āØ unit id t ā©
t ā
Ī·-unitā : Fun-Ext
ā {X : š¤ Ģ } ā μ {š¤} {X} ā map (Ī· {š¤} {X}) ā¼ id
Ī·-unitā fe t =
μ (map Ī· t) ļ¼āØreflā©
ext id (ext (Ī· ā Ī·) t) ļ¼āØ by-assoc ā©
ext (Ī» x ā ext id (Ī· (Ī· x))) t ļ¼āØ by-unit ā©
ext Ī· t ļ¼āØ ext-Ī· t ā©
t ā
where
by-assoc = (assoc id (Ī» x ā Ī· (Ī· x)) t)ā»Ā¹
by-unit = ap (Ī» - ā ext - t) (dfunext fe (Ī» x ā unit id (Ī· x)))
_ā_ : {X : š¤ Ģ } {Y : X ā š„ Ģ }
ā T X
ā ((x : X) ā T (Y x))
ā T (Ī£ x ź X , Y x)
t ā f = ext (Ī» x ā map (Ī» y ā x , y) (f x)) t
open Monad public
tensor : {ā : Universe ā Universe} (š : Monad {ā})
ā {X : š¤ Ģ } {Y : X ā š„ Ģ }
ā functor š X
ā ((x : X) ā functor š (Y x))
ā functor š (Ī£ x ź X , Y x)
tensor š = _ā_ š
syntax tensor š t f = t ā[ š ] f
\end{code}
TODO. Is "tensor" an appropriate terminology? Would (left)
convolution, in the sense of Day, be better?
https://ncatlab.org/nlab/show/tensorial+strength
https://ncatlab.org/nlab/show/Day+convolution
\begin{code}
šš : Monad
šš = record {
functor = id ;
Ī· = id ;
ext = id ;
ext-Ī· = Ī» x ā refl ;
unit = Ī» f x ā refl ;
assoc = Ī» g f x ā refl
}
ššā : {X : š¤ Ģ } {Y : X ā š„ Ģ }
(x : X)
(f : (x : X) ā (Y x))
ā x ā[ šš ] f ļ¼ x , f x
ššā x f = refl
\end{code}
If we want to call a monad T, then we can use the following module:
\begin{code}
module T-definitions {ā : Universe ā Universe} (š : Monad {ā}) where
āįµ : Universe ā Universe
āįµ = ā
T : š¤ Ģ ā āįµ š¤ Ģ
T = functor š
Ī·įµ : {X : š¤ Ģ } ā X ā T X
Ī·įµ = Ī· š
extįµ : {X : š¤ Ģ } {Y : š„ Ģ } ā (X ā T Y) ā T X ā T Y
extįµ = ext š
extįµ-Ī· : {X : š¤ Ģ } ā extįµ (Ī·įµ {š¤} {X}) ā¼ šš (T X)
extįµ-Ī· = ext-Ī· š
unitįµ : {X : š¤ Ģ } {Y : š„ Ģ } (f : X ā T Y) ā extįµ f ā Ī·įµ ā¼ f
unitįµ = unit š
assocįµ : {X : š¤ Ģ } {Y : š„ Ģ } {Z : š¦ Ģ }
(g : Y ā T Z) (f : X ā T Y)
ā extįµ (extįµ g ā f) ā¼ extįµ g ā extįµ f
assocįµ = assoc š
mapįµ : {X : š¤ Ģ } {Y : š„ Ģ } ā (X ā Y) ā T X ā T Y
mapįµ = map š
mapįµ-id : {X : š¤ Ģ } ā mapįµ (šš X) ā¼ šš (T X)
mapįµ-id = map-id š
mapįµ-ā : Fun-Ext
ā {X : š¤ Ģ } {Y : š„ Ģ } {Z : š¦ Ģ }
(f : X ā Y) (g : Y ā Z)
ā mapįµ (g ā f) ā¼ mapįµ g ā mapįµ f
mapįµ-ā = map-ā š
Ī·įµ-natural : {X : š¤ Ģ } {Y : š„ Ģ }
(f : X ā Y)
ā mapįµ f ā Ī·įµ ā¼ Ī·įµ ā f
Ī·įµ-natural = Ī·-natural š
μᵠ: {X : š¤ Ģ } ā T (T X) ā T X
μᵠ= μ š
μįµ-assoc : Fun-Ext ā {X : š¤ Ģ } ā μᵠā mapᵠμᵠ⼠μᵠā μįµ
μįµ-assoc = μ-assoc š
μįµ-natural : Fun-Ext
ā {X : š¤ Ģ } {Y : š„ Ģ }
(h : X ā Y)
ā mapįµ h ā μᵠ{š¤} {X} ⼠μᵠ{š„} {Y} ā mapįµ (mapįµ h)
μįµ-natural = μ-natural š
Ī·įµ-unitā : {X : š¤ Ģ } ā μᵠ{š¤} {X} ā Ī·įµ {āįµ š¤} {T X} ā¼ id
Ī·įµ-unitā = Ī·-unitā š
Ī·įµ-unitā : Fun-Ext
ā {X : š¤ Ģ } ā μᵠ{š¤} {X} ā mapįµ (Ī·įµ {š¤} {X}) ā¼ id
Ī·įµ-unitā = Ī·-unitā š
_āįµ_ : {X : š¤ Ģ } {Y : X ā š„ Ģ }
ā T X
ā ((x : X) ā T (Y x))
ā T (Ī£ x ź X , Y x)
_āįµ_ = _ā_ š
\end{code}
For some results, we need our monad to satisfy the condition
extįµ-const defined below. Ohad Kammar pointed out to us that this
condition is equivalent to the monad being affine. We include his
proof here.
References given by Ohad Kammar and Alex Simpson:
[1] Anders Kock, Bilinearity and Cartesian closed monads,
Math. Stand. 29 (1971) 161-174.
https://users-math.au.dk/kock/BCCM.pdf
[2]
https://www.denotational.co.uk/publications/kammar-plotkin-algebraic-foundations-for-effect-dependent-optimisations.pdf
[3] https://www.denotational.co.uk/publications/kammar-ohad-thesis.pdf
[4] Gavin Wraith mentions affine theories in his lecture notes form
1969 (Prop. 3.5 here:
https://www.denotational.co.uk/scans/wraith-algebraic-theories.pdf)
[5] Bart Jacobs' "Semantics of weakening and contraction".
https://doi.org/10.1016/0168-0072(94)90020-5
\begin{code}
module _ {ā : Universe ā Universe} (š : Monad {ā}) where
open T-definitions š
is-affine : (š¤ : Universe) ā āįµ š¤ ā š¤ Ģ
is-affine š¤ = is-equiv (Ī·įµ {š¤} {š})
ext-const' : š¤ Ģ ā š¤Ļ
ext-const' X = {š„ : Universe} {Y : š„ Ģ } (u : T Y)
ā extįµ (Ī» (x : X) ā u) ā¼ Ī» (t : T X) ā u
ext-const : š¤Ļ
ext-const = {š¤ : Universe} {X : š¤ Ģ } ā ext-const' X
affine-gives-ext-const' : Fun-Ext ā is-affine š¤ ā ext-const' š
affine-gives-ext-const' {š¤} fe a {Y} u t = γ
where
f = Ī» (x : š) ā u
I : f ā inverse (Ī·įµ {š¤} {š}) a ā¼ extįµ f
I s = (f ā inverse Ī·įµ a) s ļ¼āØ Iā ā©
extįµ f (Ī·įµ (inverse Ī·įµ a s)) ļ¼āØ Iā ā©
extįµ f s ā
where
Iā = (unitįµ f (inverse Ī·įµ a s))ā»Ā¹
Iā = ap (extįµ f) (inverses-are-sections Ī·įµ a s)
γ : extįµ f t ļ¼ u
γ = extįµ f t ļ¼āØ (ap (Ī» - ā - t) (dfunext fe I))ā»Ā¹ ā©
(f ā inverse (Ī·įµ {š¤} {š}) a) t ļ¼āØreflā©
u ā
affine-gives-ext-const : Fun-Ext ā ({š¤ : Universe} ā is-affine š¤) ā ext-const
affine-gives-ext-const fe a {š¤} {X} {š„} {Y} u t = γ
where
g : X ā T Y
g _ = u
f : T š ā T Y
f _ = u
h : š ā T Y
h _ = u
k : X ā T š
k = Ī·įµ {š¤} {š} ā unique-to-š
I : extįµ h ļ¼ f
I = dfunext fe (affine-gives-ext-const' fe a u)
γ = extįµ g t ļ¼āØreflā©
extįµ (f ā k) t ļ¼āØ ap (Ī» - ā extįµ (- ā k) t) (I ā»Ā¹) ā©
extįµ (extįµ h ā k) t ļ¼āØ assocįµ h k t ā©
extįµ h (extįµ k t) ļ¼āØ ap (Ī» - ā - (extįµ k t)) I ā©
f (extįµ k t) ļ¼āØreflā©
u ā
ext-const-gives-affine : ext-const ā is-affine š¤
ext-const-gives-affine {š¤} Ļ = γ
where
Ī·ā»Ā¹ : T š ā š
Ī·ā»Ā¹ t = ā
I : Ī·ā»Ā¹ ā Ī·įµ ā¼ id
I ā = refl
II : Ī·įµ ā Ī·ā»Ā¹ ā¼ id
II t = (Ī·įµ ā Ī·ā»Ā¹) t ļ¼āØreflā©
Ī·įµ ā ļ¼āØ (Ļ {š¤} {š} (Ī·įµ ā) t)ā»Ā¹ ā©
extįµ (Ī» x ā Ī·įµ ā) t ļ¼āØreflā©
extįµ Ī·įµ t ļ¼āØ extįµ-Ī· t ā©
t ā
γ : is-equiv (Ī·įµ {š¤} {š})
γ = qinvs-are-equivs Ī·įµ (Ī·ā»Ā¹ , I , II)
\end{code}
Monad algebras.
\begin{code}
record Algebra {ā : Universe ā Universe} (š : Monad {ā}) (A : š¦ Ģ ) : š¤Ļ where
open T-definitions š
field
structure-map : T A ā A
private
α = structure-map
field
aunit : α ā Ī· š ā¼ id
aassoc : α ā extįµ (Ī·įµ ā α) ⼠α ā extįµ id
extension : {X : š¤ Ģ } ā (X ā A) ā T X ā A
extension f = α ā mapįµ f
_extends_ : {X : š¤ Ģ } ā (T X ā A) ā (X ā A) ā š¦ ā š¤ Ģ
g extends f = g ā Ī·įµ ā¼ f
extension-property : {X : š¤ Ģ } (f : X ā A)
ā (extension f) extends f
extension-property f x =
(extension f ā Ī·įµ) x ļ¼āØreflā©
α (mapįµ f (Ī·įµ x)) ļ¼āØ ap α (Ī·įµ-natural f x) ā©
α (Ī·įµ (f x)) ļ¼āØ aunit (f x) ā©
f x ā
is-hom-from-free : {X : š¤ Ģ } ā (T X ā A) ā š¦ ā āįµ (āįµ š¤) Ģ
is-hom-from-free h = h ā μᵠ⼠α ā mapįµ h
extension-is-hom : Fun-Ext
ā {X : š¤ Ģ } (f : X ā A)
ā is-hom-from-free (extension f)
extension-is-hom fe f tt =
(extension f ā μįµ) tt ļ¼āØreflā©
(α ā mapįµ f ā μįµ) tt ļ¼āØ ap α (μįµ-natural fe f tt) ā©
(α ā μᵠā mapįµ (mapįµ f)) tt ļ¼āØ (aassoc (mapįµ (mapįµ f) tt))ā»Ā¹ ā©
(α ā mapᵠα ā mapįµ (mapįµ f)) tt ļ¼āØ ap α ((mapįµ-ā fe (mapįµ f) α tt)ā»Ā¹) ā©
(α ā mapįµ (α ā mapįµ f)) tt ļ¼āØreflā©
(α ā mapįµ (extension f)) tt ā
at-most-one-extension : Fun-Ext
ā {X : š¤ Ģ } (g h : T X ā A)
ā g ā Ī·įµ ā¼ h ā Ī·įµ
ā is-hom-from-free g
ā is-hom-from-free h
ā g ā¼ h
at-most-one-extension fe g h g-h-agreement g-is-hom h-is-hom tt =
g tt ļ¼āØreflā©
(g ā id) tt ļ¼āØ by-unitā ā»Ā¹ ā©
(g ā μᵠā mapįµ Ī·įµ) tt ļ¼āØ by-g-is-hom ā©
(α ā mapįµ g ā mapįµ Ī·įµ) tt ļ¼āØ by-functoriality ā»Ā¹ ā©
(α ā mapįµ (g ā Ī·įµ)) tt ļ¼āØ by-agreement ā©
(α ā mapįµ (h ā Ī·įµ)) tt ļ¼āØ by-functoriality-again ā©
(α ā mapįµ h ā mapįµ Ī·įµ) tt ļ¼āØ by-h-is-hom ā»Ā¹ ā©
(h ā μᵠā mapįµ Ī·įµ) tt ļ¼āØ by-unitā-again ā©
h tt ā
where
by-unitā = ap g (Ī·įµ-unitā fe tt)
by-g-is-hom = g-is-hom (mapįµ Ī·įµ tt)
by-functoriality = ap α (mapįµ-ā fe Ī·įµ g tt)
by-agreement = ap (Ī» - ā (α ā mapįµ -) tt) (dfunext fe g-h-agreement)
by-functoriality-again = ap α (mapįµ-ā fe Ī·įµ h tt)
by-h-is-hom = h-is-hom (mapįµ Ī·įµ tt)
by-unitā-again = ap h (Ī·įµ-unitā fe tt)
extension-uniqueness : Fun-Ext
ā {X : š¤ Ģ } (f : X ā A) (h : T X ā A)
ā h extends f
ā is-hom-from-free h
ā extension f ā¼ h
extension-uniqueness fe f h h-extends-f h-is-hom =
at-most-one-extension fe (extension f) h e (extension-is-hom fe f) h-is-hom
where
e : extension f ā Ī·įµ ā¼ h ā Ī·įµ
e tt = (extension f ā Ī·įµ) tt ļ¼āØ extension-property f tt ā©
f tt ļ¼āØ (h-extends-f tt)ā»Ā¹ ā©
(h ā Ī·įµ) tt ā
open Algebra public
\end{code}
Free algebras.
\begin{code}
module _ {ā : Universe ā Universe} (š : Monad {ā}) where
open T-definitions š
free : Fun-Ext ā (X : š¤ Ģ ) ā Algebra š (T X)
free fe X =
record {
structure-map = μᵠ;
aunit = Ī·įµ-unitā ;
aassoc = μįµ-assoc fe
}
is-hom : {A : š„ Ģ } {B : š¦ Ģ }
(š : Algebra š A)
(š : Algebra š B)
ā (A ā B)
ā āįµ š„ ā š¦ Ģ
is-hom š š h = h ā α ⼠β ā mapįµ h
where
α = structure-map š
β = structure-map š
monad-extension-is-hom : (fe : Fun-Ext)
{X : š¤ Ģ } {Y : š„ Ģ }
(f : X ā T Y)
ā is-hom (free fe X) (free fe Y) (extįµ f)
monad-extension-is-hom fe {X} {Y} f tt =
(extįµ f ā μįµ) tt ļ¼āØ by-ext-is-μ-map ā©
(μᵠā mapįµ f ā μįµ) tt ļ¼āØ extension-is-hom (free fe Y) fe f tt ā©
(μᵠā mapįµ (μᵠā mapįµ f)) tt ļ¼āØ again-by-ext-is-μ-map ā»Ā¹ ā©
(μᵠā mapįµ (extįµ f)) tt ā
where
by-ext-is-μ-map = ext-is-μ-map š fe f (μᵠtt)
again-by-ext-is-μ-map = ap (Ī» - ā (μᵠā mapįµ -) tt)
(dfunext fe (ext-is-μ-map š fe f))
hom-ā : Fun-Ext
ā {A : š„ Ģ } {B : š¦ Ģ } {C : š£ Ģ }
(š : Algebra š A)
(š : Algebra š B)
(š : Algebra š C)
ā (f : A ā B)
ā (g : B ā C)
ā is-hom š š f
ā is-hom š š g
ā is-hom š š (g ā f)
hom-ā fe š š š f g f-is-hom g-is-hom t =
g (f (α t)) ļ¼āØ ap g (f-is-hom t) ā©
g (β (mapįµ f t)) ļ¼āØ g-is-hom (mapįµ f t) ā©
γ (mapįµ g (mapįµ f t)) ļ¼āØ ap γ ((mapįµ-ā fe f g t)ā»Ā¹) ā©
γ (mapįµ (g ā f) t) ā
where
α = structure-map š
β = structure-map š
γ = structure-map š
extension-assoc : {A : š¦ Ģ }
(š : Algebra š A)
ā Fun-Ext
ā {X : š¤ Ģ} {Y : š„ Ģ }
(g : Y ā A) (f : X ā T Y)
ā extension š (extension š g ā f) ā¼ extension š g ā extįµ f
extension-assoc {š¦} {š¤} {š„} {A} š fe {X} {Y} g f =
extension-uniqueness š fe Ļ h h-extends-Ļ h-is-hom
where
Ļ : X ā A
Ļ = extension š g ā f
h : T X ā A
h = extension š g ā extįµ f
h-extends-Ļ : h ā Ī·įµ ā¼ Ļ
h-extends-Ļ x =
(h ā Ī·įµ) x ļ¼āØreflā©
(extension š g ā extįµ f ā Ī·įµ) x ļ¼āØ ap (extension š g) (unitįµ f x) ā©
(extension š g ā f) x ļ¼āØreflā©
Ļ x ā
h-is-hom : is-hom (free fe X) š h
h-is-hom = hom-ā fe
(free fe X) (free fe Y) š
(extįµ f) (extension š g)
(monad-extension-is-hom fe f) (extension-is-hom š fe g)
\end{code}
If we want to call an algebra (literally) α, we can used this module:
\begin{code}
module α-definitions
{ā : Universe ā Universe}
(š : Monad {ā})
{š¦ā : Universe}
(A : š¦ā Ģ )
(š : Algebra š A)
where
open T-definitions š
α : T A ā A
α = structure-map š
α-unitįµ : α ā Ī·įµ ā¼ id
α-unitįµ = aunit š
α-assocįµ : α ā extįµ (Ī·įµ ā α) ⼠α ā extįµ id
α-assocįµ = aassoc š
α-assocįµ' : α ā mapᵠα ⼠α ā μįµ
α-assocįµ' = α-assocįµ
α-extįµ : {X : š¤ Ģ } ā (X ā A) ā T X ā A
α-extįµ q = α ā mapįµ q
α-extįµ-unit : {X : š¤ Ģ }
(f : X ā A)
ā α-extįµ f ā Ī·įµ ā¼ f
α-extįµ-unit = extension-property š
α-extįµ-assoc : Fun-Ext
ā {X : š¤ Ģ } {Y : š„ Ģ }
(g : Y ā A) (f : X ā T Y)
ā α-extįµ (α-extįµ g ā f) ⼠α-extįµ g ā extįµ f
α-extįµ-assoc = extension-assoc š š
α-curryįµ : {X : š¤ Ģ } {Y : X ā š„ Ģ }
ā ((Ī£ x ź X , Y x) ā A)
ā (x : X) ā T (Y x) ā A
α-curryᵠq x = α-extᵠ(curry q x)
\end{code}
TODO. Define monad morphism (for example overline is a monad morphism
from J to K).