------------------------------------------------------------------------
-- Colimit of a setoid diagram over a quiver shape
--
-- quiver 形状上 setoid 图示的余极限
------------------------------------------------------------------------

{-# OPTIONS --safe --cubical-compatible --guardedness --exact-split --double-check #-}

module Base.SetoidColimit where

open import Agda.Primitive using (Level; _⊔_)
open import Agda.Builtin.Sigma using (Σ; _,_)
open import Function.Bundles using (Func; _⟨$⟩_)
open import Relation.Binary.Core using (Rel)
open import Relation.Binary.Bundles using (Setoid)
open import Relation.Binary.Construct.Closure.Equivalence using
  (setoid; return; symmetric; gfold)

open Func using (cong)
open Setoid using (Carrier; isEquivalence)

module _ {k c ℓ q : Level}
         (K : Set k)
         (Q : K → K → Set q)
         (D : K → Setoid c ℓ)
         (D₁ : ∀ {x y} → Q x y → Func (D x) (D y)) where

  ----------------------------------------------------------------------
  -- Disjoint union of the fibres
  --
  -- An element carries its birth vertex.
  --
  -- 各纤维的不交并
  --
  -- 元素携带其诞生顶点。

  ColimCarrier : Set (k ⊔ c)
  ColimCarrier = Σ K λ x → Carrier (D x)

  ----------------------------------------------------------------------
  -- Generating identification
  --
  -- Within-fibre equality, or one arrow step.
  --
  -- 生成性识别
  --
  -- 纤维内相等,或沿一条箭头前进一步。

  data _∼₀_ : Rel ColimCarrier (k ⊔ c ⊔ q ⊔ ℓ) where
    same : ∀ {x} {a a' : Carrier (D x)}
         → Setoid._≈_ (D x) a a'
         → (x , a) ∼₀ (x , a')
    edge : ∀ {x y} (f : Q x y) {a : Carrier (D x)}
         → (x , a) ∼₀ (y , D₁ f ⟨$⟩ a)

  ----------------------------------------------------------------------
  -- The colimit setoid
  --
  -- The equivalence closure of the generators. The carrier is never
  -- collapsed, so no HIT, univalence, K or transport is needed, and
  -- the fibres may carry arbitrary setoids. Collapsing the closure
  -- to propositional equality on a bare Set is a separate theorem
  -- needing a HIT and a non-UIP fibre, hence independent of the
  -- flags.
  --
  -- 余极限 setoid
  --
  -- 生成子的等价闭包。载体从不被压合,故无需 HIT、univalence、K 或
  -- 传输,纤维可带任意 setoid。把闭包压成裸 Set 上的命题相等是另一
  -- 个定理,需要 HIT 与非 UIP 纤维,故与开关独立。

  Colim : Setoid (k ⊔ c) (k ⊔ c ⊔ q ⊔ ℓ)
  Colim = setoid _∼₀_

  ----------------------------------------------------------------------
  -- Leg of the canonical cocone
  --
  -- Tag an element with its vertex.
  --
  -- 规范余锥的腿
  --
  -- 给元素打上顶点标签。

  inj : (x : K) → Func (D x) Colim
  inj x = record
    { to   = λ a → x , a
    ; cong = λ a≈ → return (same a≈)
    }

  ----------------------------------------------------------------------
  -- Canonical cocone commutation
  --
  -- The image along f is the same element reached by one edge step,
  -- read backwards.
  --
  -- 规范余锥交换
  --
  -- 沿 f 的像即走一条 edge 后到达的同一元素(反向读取)。

  canonical-comm : ∀ {x y} (f : Q x y) {a : Carrier (D x)}
    → Setoid._≈_ Colim (y , D₁ f ⟨$⟩ a) (x , a)
  canonical-comm f {a} = symmetric _∼₀_ (return (edge f {a}))

  module Cocone {cN ℓN : Level} (N : Setoid cN ℓN) where

    ------------------------------------------------------------------
    -- A cocone
    --
    -- A leg out of every fibre, agreeing along every arrow.
    --
    -- 余锥
    --
    -- 每条纤维一条腿,且沿任意箭头相容。

    record Cocone : Set (k ⊔ c ⊔ ℓ ⊔ q ⊔ cN ⊔ ℓN) where
      field
        ψ    : (x : K) → Func (D x) N
        comm : ∀ {x y} (f : Q x y) {a : Carrier (D x)}
             → Setoid._≈_ N (ψ y ⟨$⟩ (D₁ f ⟨$⟩ a))
                            (ψ x ⟨$⟩ a)

    open Cocone

    ------------------------------------------------------------------
    -- The mediating map on representatives
    --
    -- Defined on representatives, then closed under the generators:
    -- same uses the leg's congruence, edge uses commutation.
    --
    -- 代表元上的中介映射
    --
    -- 先在代表元上定义,再对生成子封闭:
    -- same 用腿的同余,edge 用交换律。

    rep : (cn : Cocone) → ColimCarrier → Carrier N
    rep cn (x , a) = ψ cn x ⟨$⟩ a

    rep-step : (cn : Cocone) → ∀ {u v} → u ∼₀ v
             → Setoid._≈_ N (rep cn u) (rep cn v)
    rep-step cn (same a≈)    = cong (ψ cn _) a≈
    rep-step cn (edge f {a}) = Setoid.sym N (comm cn f {a})

    ------------------------------------------------------------------
    -- Unique mediating morphism
    --
    -- The fold extends rep over the closure.
    --
    -- 唯一 mediate 态射
    --
    -- fold 把 rep 扩张到整个等价闭包。

    mediate : (cn : Cocone) → Func Colim N
    mediate cn = record
      { to   = rep cn
      ; cong = gfold (isEquivalence N) (rep cn) (rep-step cn)
      }

    ------------------------------------------------------------------
    -- Factorisation
    --
    -- Mediating after the leg is the leg, definitionally.
    --
    -- 因子分解
    --
    -- mediate 复合腿即该腿(定义性成立)。

    factor : (cn : Cocone) (x : K) {a : Carrier (D x)}
      → Setoid._≈_ N (mediate cn ⟨$⟩ (x , a)) (ψ cn x ⟨$⟩ a)
    factor cn x = Setoid.refl N

    ------------------------------------------------------------------
    -- Uniqueness
    --
    -- Any morphism agreeing with the legs on every fibre agrees with
    -- mediate at every tagged representative.
    --
    -- 唯一性
    --
    -- 任何在每条纤维上与各腿一致的态射,在每个带标签代表元上都与
    -- mediate 一致。

    unique : (cn : Cocone) (h : Func Colim N)
      → (∀ (x : K) {a : Carrier (D x)}
           → Setoid._≈_ N (h ⟨$⟩ (x , a)) (ψ cn x ⟨$⟩ a))
      → ∀ (u : ColimCarrier)
      → Setoid._≈_ N (h ⟨$⟩ u) (mediate cn ⟨$⟩ u)
    unique cn h fac (x , a) = fac x