open import Level

open import Data.Nat hiding (fold)
open import Data.Fin hiding (fold ; lift )
open import Data.Product
open import Data.Sum
open import Data.Unit

open import Relation.Binary.PropositionalEquality

open import Chapter2.Logic
open import Chapter2.IProp

open import Chapter5.IDesc
open import Chapter5.IDesc.Fixpoint
open import Chapter5.IDesc.InitialAlgebra
open import Chapter5.IDesc.Lifting
open import Chapter5.IDesc.Induction

open import Chapter8.Ornament.Examples.Lifting hiding ([_]^) renaming ([_]^h to [_]^ho)
open import Chapter8.Ornament

module Chapter8.AlgebraicOrnament.Coherence
           {ℓ : Level}
           {K : Set ℓ}
           {X : K → Set ℓ}
           (D : func ℓ K K)
           (α : ⟦ D ⟧func X ⇒ X) where

open import Chapter8.AlgebraicOrnament
open import Chapter8.Ornament.Algebra {u = proj₁} (algOrn D α)
open import Chapter8.Ornament.CartesianMorphism

-- Thanks to Andrea Vezzosi for the proof!

coherentOrn : ∀{k x} → 
                (t : μ (algOrnD D α) (k , x)) → 
                ⊢ x ≡ fold D α (forgetOrnament t)
coherentOrn = induction (algOrnD D α) P
                        (λ {i}{xs} → step {i} {xs})

    where P : {kx : Σ K X} → μ (algOrnD D α) kx → Set ℓ
          P {(k , x)} t = ⊢ x ≡ fold D α (forgetOrnament t)

          step' : (kx : Σ K X)
                  (D' : IDesc ℓ K)
                  (α' : ⟦ D' ⟧ X → X (proj₁ kx)) →
                  let algOrnD' : IDesc ℓ (Σ K X)
                      algOrnD' =  Desc.algOrnD (proj₁ kx) (proj₂ kx) D' α' in
                  (xs : ⟦ algOrnD' ⟧ (μ (algOrnD D α))) →
                  [  algOrnD' ]^h (λ {kx} t → ⊢ proj₂ kx ≡ fold D α  (forgetOrnament t)) xs →
                  ⊢ proj₁ xs ≡ Fold.hyps D α D' 
                                           (forgetOrnNat (algOrn D α) ([ D' ]^ho (proj₁ xs))
                                             (Fold.hyps (algOrnD D α) ornAlgebra ⟦ [ D' ]^ho (proj₁ xs) ⟧Orn  (proj₂ (proj₂ xs))))
          step' (k , x) (`var i) α' (xs , q , xxs) ih = ih
          step' (k , x) `1  α' (lift tt , q , lift tt) (lift tt) = pf refl
          step' (k , x) (D₁ `× D₂)  α' 
                ((xs₁ , xs₂) , q  , xxs₁ , xxs₂) (ih₁ , ih₂) = 
                cong₂ (λ x y → (x , y)) <$>
                  step' (k , x) D₁ (λ xs₁ → α' (xs₁ , xs₂)) (xs₁ , q , xxs₁) ih₁ ⊛ 
                  step' (k , x) D₂ (λ xs₂ → α' (xs₁ , xs₂)) (xs₂ , q , xxs₂) ih₂
          step' (k , x) (`σ n T)  α' ((s , xs) , q , xxs) ih = 
                cong⊢ (λ x → s , x) 
                      (step' (k , x) (T s) (λ xs → α' (s , xs)) (xs , q , xxs) ih)
          step' (k , x) (`Σ S T)  α' ((s , xs) , q , xxs) ih = 
                cong⊢ (λ x → s , x) 
                      (step' (k , x) (T s) (λ xs → α' (s , xs)) (xs , q , xxs) ih)
          step' (k , .(α' f)) (`Π S T)  α' (f , refl , xxs) ih = 
                extensionality (λ s → 
                  step' (k , α' f) (T s) (λ xs → α' f ) (f s , refl , (xxs s)) (ih s))

          step : DAlg (algOrnD D α) P
          step {(k , .(α xs))} {(xs , refl , xxs)} ih =
            cong⊢ α (step' (k , α xs) 
                           (func.out D k) (α {k}) 
                           ((xs , refl ,  xxs)) ih)