可換モノイドにおける等式
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