Skip to content

可換モノイドにおける等式

open import commutative-monoid

module commutative-monoid-equation (M : CommutativeMonoid) where

open import apartness-relation
open import natural-number
open import fin
open import vector
open import sigma-type
open import identity-type
open import commutative-monoid-properties M
open CommutativeMonoidStr (M .snd)
open ApartedSet (M .fst)
infixl 60 _□_
data Expr (n : ℕ) : Set where
  var : Fin n → Expr n
  _□_ : Expr n → Expr n → Expr n
  ϵ : Expr n

varLit : ∀ {n} → (m : ℕ) → ∀ {x : ≤ℕRec m n} → Expr n
varLit m {x = x} = var (FinLit m {x = x})

Normal : ℕ → Set
Normal n = Vec ℕ n

private variable
  n : ℕ

eval : Expr n → Vec (^ M) n → ^ M
eval (var p) env = lookup p env
eval (x □ y) env = eval x env · eval y env
eval ϵ       env = empty

zeros : ∀ n → Normal n
zeros zero    = []
zeros (suc n) = zero ∷ zeros n

sing : Fin n → Normal n
sing zero    = suc zero ∷ zeros _
sing (suc p) = zero ∷ sing p

overlay : Normal n → Normal n → Normal n
overlay []       []       = []
overlay (x ∷ xs) (y ∷ ys) = x +ℕ y ∷ overlay xs ys

normalize : Expr n → Normal n
normalize (var p) = sing p
normalize (x □ y) = overlay (normalize x) (normalize y)
normalize ϵ       = zeros _

times : ℕ → ^ M → ^ M
times zero    x = empty
times (suc n) x = x · times n x

times-+ : ∀ (m n : ℕ) x → times (m +ℕ n) x ≈ times m x · times n x
times-+ zero    _ _ = sym-≈ lunit
times-+ (suc m) n x =
  trans-≈ (·-pres-∼ᵣ _ .fst (times-+ m n x)) (sym-≈ assoc)

evalNormal : Normal n → Vec (^ M) n → ^ M
evalNormal []       _         = empty
evalNormal (x ∷ xs) (a ∷ env) = times x a · evalNormal xs env

private
  helper : ∀ n env → evalNormal (zeros n) env ≈ empty
  helper zero    env       = refl-≈ empty
  helper (suc n) (x ∷ env) = trans-≈ lunit (helper n env)

  lemma1 : ∀ (p : Fin n) env → evalNormal (sing p) env ≈ lookup p env
  lemma1 zero (x ∷ env) = k
    where
      k : times (suc zero) x · evalNormal (zeros _) env ≈ x
      k =
        trans-≈
          (·-pres-∼ᵣ (times (suc zero) x) .fst (helper _ env))
          (trans-≈ runit runit)
  lemma1 (suc p) (x ∷ env) =
    trans-≈ lunit
      (trans-≈ (lemma1 p env) (sym-≈ (id→equiv (lookup-suc p x env))))

  lemma2 : ∀ (xs ys : Normal n) env
    → evalNormal (overlay xs ys) env
      ≈ (evalNormal xs env · evalNormal ys env)
  lemma2 [] [] env = sym-≈ lunit
  lemma2 (x ∷ xs) (y ∷ ys) (v ∷ env) = k
    where
      k : times (x +ℕ y) v · evalNormal (overlay xs ys) env
        ≈ times x v · evalNormal xs env · (times y v · evalNormal ys env)
      k = trans-≈ (·-pres-∼ₗ (evalNormal (overlay xs ys) env) .fst (times-+ x y v))
            (trans-≈ (·-pres-∼ᵣ _ .fst (lemma2 xs ys env)) swap-center)

  lemma : ∀ (x : Expr n) env → evalNormal (normalize x) env ≈ eval x env
  lemma (var p) env = lemma1 p env
  lemma (x □ y) env = k
    where
      k1 : evalNormal (normalize x) env ≈ eval x env
      k1 = lemma x env

      k2 : evalNormal (normalize y) env ≈ eval y env
      k2 = lemma y env

      k : evalNormal (overlay (normalize x) (normalize y)) env ≈ eval x env · eval y env
      k = trans-≈ (trans-≈ (lemma2 (normalize x) _ env) (·-pres-∼ᵣ _ .fst k2)) (·-pres-∼ₗ (eval y env) .fst k1)
  lemma ϵ env = helper _ env

eval-equality : ∀ (x y : Expr n) env → normalize x = normalize y → eval x env ≈ eval y env
eval-equality x y env p =
  trans-≈ (sym-≈ k1)
    (trans-≈ (id→equiv k3) k2)
  where
    k1 : evalNormal (normalize x) env ≈ eval x env
    k1 = lemma x env

    k2 : evalNormal (normalize y) env ≈ eval y env
    k2 = lemma y env

    k3 : evalNormal (normalize x) env = evalNormal (normalize y) env
    k3 = cong (λ w → evalNormal w env) p