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).