Agda 在列表上的统一

Question

我正在做一个项目来证明正则表达式的一些属性。 这是我的部分代码

⇨这里表示派生，Regexp ⇨ word表示一个Regexp可以派生一个词

Σ : Set
Σ* : List Σ

下面定义了拼接e₁ ∙ e₂可以派生出单词w的情况if e₁ ⇨ w₁, e₂ ⇨ w₂ and w ≡ w₁ ++ w₂

data _⇨_ : RegExp Σ → Σ* → Set where
 con : {e₁ e₂ : RegExp Σ}{w w₁ w₂ : Σ*} → w ≡ w₁ ++ w₂ → e₁ ⇨ w₁ → e₂ ⇨ w₂ → e₁ ∙ e₂ ⇨ w

这证明如果 w ≡ w₁ ++ [] 和 (e₁ 不能导出 w₁) 则 (e₁.e₂ 不能导出 w)

¬e₁∙e₂⇨xs[]ˡ : {e₁ e₂ : RegExp Σ}{w w₁ : Σ*} → w ≡ w₁ ++ [] → ¬ (e₁ ⇨ w₁) → ¬ (e₁ ∙ e₂ ⇨ w)
¬e₁∙e₂⇨xs[]ˡ refl ¬e₁⇨w₁ (con {w₂ = []} refl e₁⇨w₁ e₂⇨[]) = ¬e₁⇨w₁ e₁⇨w₁

然而，con refl e₁⇨w₁ e₂⇨[]中的refl并没有进行类型检查，因为Agda无法统一¬e₁∙e₂⇨xs[]ˡ中的w₁和[中的w₁ =27=] 错误信息在这里：

w₁ != w₂ of type List Σ
when checking that the pattern refl has type w₁ ++ [] ≡ w₂ ++ []

任何帮助将不胜感激！

Answer 1

在 w ≡ w₁ ++ [] 上进行模式匹配后你就完蛋了，因为 w 与 w₁ ++ [] 统一，e₁ ∙ e₂ ⇨ w 变为 e₁ ∙ e₂ ⇨ w₁ ++ []，你可以' t 模式匹配。

_++_ 不是单射的并且 w₁ ++ [] ≡ w₁' ++ w₂' 不包含 w₁ ≡ w₁' × [] ≡ w₂' — 通常还有其他方法可以统一这两个表达式。

你的引理同构于

¬e₁∙e₂⇨xs[]ˡ : {e₁ e₂ : RegExp Σ}{w : Σ*} → ¬ (e₁ ⇨ w) → ¬ (e₁ ∙ e₂ ⇨ w)

这在我看来是错误的。

有关类似问题，请参阅 。