open import Cat.Diagram.Monad.Relative
open import Cat.Diagram.Monad
open import Cat.Prelude

import Cat.Reasoning

open Functor
open _=>_

module Cat.Diagram.Monad.Extension where

module _ {o ℓ} (C : Precategory o ℓ) where

Extension systems🔗

An extension system on a category $C$ is an alternative way of presenting a monad on $C .$ As the name suggests, extension systems are built around an extension operation, of type $C (X, M Y) \to C (MX, M Y),$ in place of the multiplication operation $C (MMX, MX)$ that characterises a monad. This has a couple of immediate benefits:

The extension operation avoids nested applications of $M,$ which tends to improve ergonomics.
The extension operation $C (X, M Y) \to C (MX, M Y)$ simultaneously encodes both $M ’s$ multiplication and its underlying functorial action, which reduces the amount of data that needs to be given explicitly.
It is not immediately clear how to generalize monads beyond endofunctors. In constrast, extension systems can be readily generalized to relative extension systems ¹.

With that bit of motivation out of the way, we shall proceed to define extension systems. An extension system consists of:

A mapping of objects, $M : C \to C;$ and
A family of morphisms $η_{X} : C (X, MX),$ called the unit of the extension system; and
The extension operation, $(-)^{M} : C (X, M Y) \to C (MX, M Y) .$ Gesturing towards the “monads” found in functional programming, we will call this operation bind.

Note that we do not require the mapping of objects to be functorial, nor the do we require the unit to be natural. Instead, we impose 3 equations on this structure:²

For every $X : C,$ we must have $(η_{X})^{M} = id_{MX};$
For every $f : C (X, M Y),$ we must have $f^{M} \circ η_{X} = f;$ and
For every $f : C (Y, MX),$ and $g : C (X, M Y),$ we must have $f^{M} \circ g^{M} = (f^{M} \circ g)^{M} .$

For reasons of generality, we shall define extension systems as relative extension systems, along the identity functor. Even though we use a more general definition, the data contained in an extension system is precisely the data listed above.

Extension-system : ∀ {o ℓ} → Precategory o ℓ → Type (o ⊔ ℓ)
Extension-system C = Relative-extension-system (Id {C = C})

module Extension-system {o ℓ} {C : Precategory o ℓ} (E : Extension-system C) where
  open Cat.Reasoning C
  open Relative-extension-system E public

We can recover the monad’s multiplication by extending the identity morphism $id_{MX} : C (MX, MX) .$

  join : ∀ {x} → Hom (M₀ (M₀ x)) (M₀ x)
  join {x} = bind (id {M₀ x})

Naturality of join also follows, though is a bit more involved.

  join-natural
    : ∀ {x y} (f : Hom x y)
    → join ∘ M₁ (M₁ f) ≡ M₁ f ∘ join
  join-natural f =
    bind id ∘ bind (unit ∘ bind (unit ∘ f)) ≡⟨ bind-∘ id (unit ∘ bind (unit ∘ f)) ⟩
    bind (bind id ∘ unit ∘ bind (unit ∘ f)) ≡⟨ ap bind (cancell (bind-unit-∘ id) ∙ sym (idr _)) ⟩
    bind (bind (unit ∘ f) ∘ id)             ≡˘⟨ bind-∘ (unit ∘ f) id ⟩
    bind (unit ∘ f) ∘ bind id               ∎

Equivalence with monads🔗

module _ {o ℓ} {C : Precategory o ℓ} where
  open Cat.Reasoning C

It remains to show that monads on $C$ are equivalent to extension systems on $C .$ We’ll start with the forward direction. Throughout, let $M$ be a fixed monad on $C .$

  Monad→Extension-system : Monad C → Extension-system C
  Monad→Extension-system M = system where
    module M = Monad M
    open Extension-system

The mapping of objects, and the unit, are directly given by (the object part of) $M -qua-endofunctor,$ and by the unit natural transformation.

    system : Extension-system C
    system .M₀ = M.M₀
    system .unit = M.η _

Defining the extension operation is slightly trickier, but not by much. If we have a morphism $f : C (X, M Y),$ then its extension is defined to be composite

MX M f MM Y μ M Y .

    system .bind f = M.μ _ ∘ M.M₁ f

Finally, a few short computations show that this definition is lawful.

    system .bind-unit-id =
      M.μ _ ∘ M.M₁ (M.η _) ≡⟨ M.left-ident ⟩
      id                             ∎
    system .bind-unit-∘ f =
      (M.μ _ ∘ M.M₁ f) ∘ M.η _ ≡⟨ pullr (sym $ M.unit.is-natural _ _ _) ⟩
      M.μ _ ∘ M.η _ ∘ f        ≡⟨ cancell M.right-ident ⟩
      f                        ∎
    system .bind-∘ f g =
      (M.μ _ ∘ M.M₁ f) ∘ (M.μ _ ∘ M.M₁ g)             ≡⟨ pullr (extendl (sym $ M.mult.is-natural _ _ _)) ⟩
      M.μ _ ∘ M.μ _ ∘ (M.M₁ (M.M₁ f) ∘ M.M₁ g)        ≡⟨ extendl (sym M.mult-assoc) ⟩
      M.μ _ ∘ M.M₁ (M.μ _) ∘ (M.M₁ (M.M₁ f) ∘ M.M₁ g) ≡⟨ ap₂ _∘_ refl (pulll (sym (M.M-∘ _ _)) ∙ sym (M.M-∘ _ _)) ⟩
      M.μ _ ∘ M.M₁ ((M.μ _ ∘ M.M₁ f) ∘ g)             ∎

Constructing a monad from an extension system is simply a matter of bolting together our results from the previous section.

  Extension-system→Monad : Extension-system C → Monad C
  Extension-system→Monad E = monad where
    module E = Extension-system E
    open Monad

    monad : Monad C
    monad .M = E.M
    monad .unit .η x = E.unit
    monad .unit .is-natural _ _ f = E.unit-natural f
    monad .mult .η x = E.join
    monad .mult .is-natural _ _ f = E.join-natural f

The monad laws follow from another short series of computations.

    monad .left-ident =
      E.bind id ∘ E.bind (E.unit ∘ E.unit) ≡⟨ E.bind-∘ _ _ ⟩
      E.bind (E.bind id ∘ E.unit ∘ E.unit) ≡⟨ ap E.bind (cancell (E.bind-unit-∘ id)) ⟩
      E.bind E.unit                        ≡⟨ E.bind-unit-id ⟩
      id                                   ∎
    monad .right-ident =
      E.bind id ∘ E.unit ≡⟨ E.bind-unit-∘ id ⟩
      id                 ∎
    monad .mult-assoc =
      E.bind id ∘ E.bind (E.unit ∘ E.bind id) ≡⟨ E.bind-∘ _ _ ⟩
      E.bind (E.bind id ∘ E.unit ∘ E.bind id) ≡⟨ ap E.bind (cancell (E.bind-unit-∘ id) ∙ sym (idr _)) ⟩
      E.bind (E.bind id ∘ id)                 ≡˘⟨ E.bind-∘ _ _ ⟩
      E.bind id ∘ E.bind id                   ∎

Moreover, these two functions constitute an equivalence between monads on $C$ and extension systems on $C .$ In light of this fact, we will silently identify monads and extension systems, whenever it is convenient.

  Monad≃Extension-system : Monad C ≃ Extension-system C
  Monad≃Extension-system = Iso→Equiv $
    Monad→Extension-system ,
    iso Extension-system→Monad
      (λ E →
        let module E = Extension-system E in
        Relative-extension-system-path
          (λ _ → refl)
          (λ _ → refl)
          (λ f →
            E.bind id ∘ E.bind (E.unit ∘ f i0) ≡⟨ E.bind-∘ id (E.unit ∘ f i0) ⟩
            E.bind (E.bind id ∘ E.unit ∘ f i0) ≡⟨ ap E.bind (cancell (E.bind-unit-∘ id)) ⟩
            E.bind (f i0)                      ≡⟨ ap E.bind (coe0→1 (λ i → f i0 ≡ f i) refl) ⟩
            E.bind (f i1)                      ∎))
      (λ M →
        let module M = Monad M in
        Monad-path
          (λ _ → refl)
          (λ f →
            M.μ _ ∘ M.M₁ (M.η _ ∘ f)        ≡⟨ pushr (M.M-∘ _ _) ⟩
            (M.μ _ ∘ M.M₁ (M.η _)) ∘ M.M₁ f ≡⟨ eliml M.left-ident ⟩
            M.M₁ f ∎)
          (λ _ → refl)
          (λ _ → elimr M.M-id))

Algebras over an extension system🔗

An extension algebra over $E$ is the extension system analog of a algebra over a monad. Following the general theme of extension operations, an extension algebra on $X : C$ is given by an operation $ν : C (A, X) \to C (M A, X) .$ Intuitively, this operation lets us “evaluate” any $M,$ so long as the codomain of the evaluation is $X .$

This operation must satisfy a pair of equations:

For every $f : C (A, X),$ we have $ν (f) \circ η_{A} = f;$ and
For every $f : C (B, X),$ and $g : C (A, MB),$ we have $ν (f) \circ g^{M} = ν (ν f \circ g) .$

As with extension systems, we define extension algebras in terms of relative extension algebras.

Extension-algebra-on
  : ∀ {o ℓ} {C : Precategory o ℓ}
  → (open Precategory C)
  → Extension-system C
  → Ob
  → Type (o ⊔ ℓ)
Extension-algebra-on = Relative-algebra-on

module Extension-algebra-on
  {o ℓ} {C : Precategory o ℓ} (open Cat.Reasoning C)
  {E : Extension-system C} {x : Ob} (α : Extension-algebra-on E x)
  where
  open Extension-system E
  open Relative-algebra-on α public

The evaluation map also interacts well with the multiplication.

  ν-join : ∀ {a} (f : Hom a x) → ν f ∘ join ≡ ν (ν f)
  ν-join f =
    ν f ∘ bind id ≡⟨ ν-bind f id ⟩
    ν (ν f ∘ id)  ≡⟨ ap ν (idr _) ⟩
    ν (ν f)       ∎

Equivalence with monad algebras🔗

module _ {o ℓ} {C : Precategory o ℓ} {E : Extension-system C} where
  open Cat.Reasoning C
  open Extension-system E
  open Extension-algebra-on

As the name suggests, extension algebras over $E$ are equivalent to monad algebras over the canonical monad associated with $E .$

For the forward direction, let $α : MX \to X$ be a monad algebra over $E .$ We can obtain the required extension operation $ν$ by sending each $f : C (A, X)$ to the composite

M A M f MX α X .

  Algebra-on→Extension-algebra-on
    : ∀ {x}
    → Algebra-on C (Extension-system→Monad E) x
    → Extension-algebra-on E x
  Algebra-on→Extension-algebra-on {x = x} α = ext-alg where
    module α = Algebra-on α
    open Extension-algebra-on

    ext-alg : Extension-algebra-on E x
    ext-alg .ν f = α.ν ∘ M₁ f

The monad algebra laws follow from some tedious calculations that we shall omit.

    ext-alg .ν-unit f =
      (α.ν ∘ M₁ f) ∘ unit ≡⟨ pullr (sym $ unit-natural f) ⟩
      α.ν ∘ unit ∘ f      ≡⟨ cancell α.ν-unit ⟩
      f ∎
    ext-alg .ν-bind f g =
      (α.ν ∘ M₁ f) ∘ bind g                    ≡⟨ pullr (bind-naturall _ _) ⟩
      α.ν ∘ bind ⌜ M₁ f ∘ g ⌝                  ≡⟨ ap! (insertl (bind-unit-∘ id)) ⟩
      α.ν ∘ bind (join ∘ unit ∘ M₁ f ∘ g)      ≡⟨ pushr (sym (bind-∘ _ _)) ⟩
      (α.ν ∘ join) ∘ bind (unit ∘ M₁ f ∘ g)    ≡⟨ pushl (sym $ α.ν-mult) ⟩
      α.ν ∘ M₁ α.ν ∘ bind (unit ∘ M₁ f ∘ g)    ≡⟨ ap (α.ν ∘_) (bind-naturall _ _) ⟩
      α.ν ∘ bind ⌜ M₁ α.ν ∘ unit ∘ M₁ f ∘ g ⌝  ≡⟨ ap! (centralizel (sym $ unit-natural _)) ⟩
      α.ν ∘ bind (unit ∘ (α.ν ∘ M₁ f) ∘ g)     ∎

Conversely, a monad algebra over $E$ can be derived from an extension algebra $ν : C (A, X) \to C (M A, X)$ over $E$ by restricting to $ν (id_{X}) : C (MX, X) .$

  Extension-algebra-on→Algebra-on
    : ∀ {x}
    → Extension-algebra-on E x
    → Algebra-on C (Extension-system→Monad E) x
  Extension-algebra-on→Algebra-on {x = x} α = alg where
    module α = Extension-algebra-on α
    open Algebra-on

    alg : Algebra-on C (Extension-system→Monad E) x
    alg .ν = α.ν id

The proofs of the monad algebra laws are mercifully short.

    alg .ν-unit = α.ν-unit id
    alg .ν-mult =
      α.ν id ∘ M₁ (α.ν id) ≡⟨ α.ν-natural _ _ ⟩
      α.ν (id ∘ α.ν id)    ≡⟨ ap α.ν (idl _) ⟩
      α.ν (α.ν id)         ≡˘⟨ α.ν-join id ⟩
      α.ν id ∘ join ∎

As expected, these two functions constitute an equivalence between monad algebras and extension algebras.

  Algebra-on≃Extension-algebra-on
    : ∀ {x}
    → Algebra-on C (Extension-system→Monad E) x ≃ Extension-algebra-on E x
  Algebra-on≃Extension-algebra-on {x} = Iso→Equiv $
    Algebra-on→Extension-algebra-on ,
    iso Extension-algebra-on→Algebra-on
      (λ α →
        let module α = Extension-algebra-on α in
        Relative-algebra-on-pathp refl λ f →
          α.ν id ∘ M₁ (f i0) ≡⟨ α.ν-natural _ _ ⟩
          α.ν (id ∘ f i0)    ≡⟨ ap α.ν (idl _) ⟩
          α.ν (f i0)         ≡⟨ ap α.ν (coe0→1 (λ i → f i0 ≡ f i) refl) ⟩
          α.ν (f i1)         ∎)
      (λ α →
        let module α = Algebra-on α in
        Algebra-on-pathp C refl $
          α.ν ∘ bind (unit ∘ id) ≡⟨ elimr (ap bind (idr _) ∙ bind-unit-id) ⟩
          α.ν                    ∎)

In fact, we will define extension systems as a special case of relative extension systems!↩︎
contrast this with the 7 equations required for a monad: 2 for functoriality, 2 for naturality, and 3 for unitality/associativity↩︎