我在使用字符串可确定性时遇到麻烦。首先,我感到困惑,为什么在阿格达(Agda)中难以决定性工作,而在Coq中看起来却像黄油一样光滑。当我尝试证明有关字符串的简单定理时,Agda会展开这种混乱的定义,除非您确切知道要执行的操作,否则几乎无法使用该定义。如何通过模式匹配使字符串保持可决定性,从而使定义保持原样?
我使用的是Stump的keep函数,而不是Agda的检查。
keep : ∀{ℓ}{A : Set ℓ} → (x : A) → Σ A (λ y → x ≡ y)
keep x = ( x , refl )
--first roadblock
eqbStringrefl' : forall (b : String) → true ≡ (b == b)
eqbStringrefl' b with keep (b ≟ b)
eqbStringrefl' b | (.true Relation.Nullary.because Relation.Nullary.ofʸ refl) , snd = {!!}
eqbStringrefl' b | (.false Relation.Nullary.because Relation.Nullary.ofⁿ ¬p) , snd = {!!}
这是阿格达的输出:
-- Goal: true ≡
-- Relation.Nullary.Decidable.Core.isYes
-- (Relation.Nullary.Decidable.Core.map′
-- (λ x →
-- Agda.Builtin.String.Properties.primStringToListInjective b b
-- (Data.List.Relation.Binary.Pointwise.Pointwise-≡⇒≡
-- (Data.List.Relation.Binary.Pointwise.map
-- (λ {z} {z = z₁} →
-- Agda.Builtin.Char.Properties.primCharToNatInjective z z₁)
-- x)))
-- (λ x →
-- Data.List.Relation.Binary.Pointwise.map
-- (cong Agda.Builtin.Char.primCharToNat)
-- (Data.List.Relation.Binary.Pointwise.≡⇒Pointwise-≡
-- (cong Data.String.toList x)))
-- (Data.List.Relation.Binary.Pointwise.decidable
-- (λ x y →
-- Relation.Nullary.Decidable.Core.map′
-- (Data.Nat.Properties.≡ᵇ⇒≡ (Agda.Builtin.Char.primCharToNat x)
-- (Agda.Builtin.Char.primCharToNat y))
-- (Data.Nat.Properties.≡⇒≡ᵇ (Agda.Builtin.Char.primCharToNat x)
-- (Agda.Builtin.Char.primCharToNat y))
-- (Data.Bool.Properties.T?
-- (Agda.Builtin.Char.primCharToNat x Data.Nat.≡ᵇ
-- Agda.Builtin.Char.primCharToNat y)))
-- (Data.String.toList b) (Data.String.toList b)))
-- ————————————————————————————————————————————————————————————
-- snd : Relation.Nullary.Decidable.Core.map′
-- (λ x →
-- Agda.Builtin.String.Properties.primStringToListInjective b b
-- (Data.List.Relation.Binary.Pointwise.Pointwise-≡⇒≡
-- (Data.List.Relation.Binary.Pointwise.map
-- (λ {z} {z = z₁} →
-- Agda.Builtin.Char.Properties.primCharToNatInjective z z₁)
-- x)))
-- (λ x →
-- Data.List.Relation.Binary.Pointwise.map
-- (cong Agda.Builtin.Char.primCharToNat)
-- (Data.List.Relation.Binary.Pointwise.≡⇒Pointwise-≡
-- (cong Data.String.toList x)))
-- (Data.List.Relation.Binary.Pointwise.decidable
-- (λ x y →
-- Relation.Nullary.Decidable.Core.map′
-- (Data.Nat.Properties.≡ᵇ⇒≡ (Agda.Builtin.Char.primCharToNat x)
-- (Agda.Builtin.Char.primCharToNat y))
-- (Data.Nat.Properties.≡⇒≡ᵇ (Agda.Builtin.Char.primCharToNat x)
-- (Agda.Builtin.Char.primCharToNat y))
-- (Data.Bool.Properties.T?
-- (Agda.Builtin.Char.primCharToNat x Data.Nat.≡ᵇ
-- Agda.Builtin.Char.primCharToNat y)))
-- (Data.String.toList b) (Data.String.toList b))
-- ≡ Relation.Nullary.yes refl
-- b : String
如果现在我进行重写,则目标被简化了,但假设列表中仍然有些混乱。当我尝试ctrl-a时,尽管目标似乎是不可推断的,但仍收到以下错误:
Goal: true ≡ true
Not implemented: The Agda synthesizer (Agsy) does not support
copatterns yet
尽管如此,我仍然可以继续使用snd术语,这似乎很干净,然后只需应用基本规则即可得出最终证明。
eqbStringrefl'' : forall (b : String) → true ≡ (b == b)
eqbStringrefl'' b with keep (b ≟ b)
eqbStringrefl'' b | (.true Relation.Nullary.because Relation.Nullary.ofʸ refl) , snd rewrite snd = {!!}
eqbStringrefl'' b | (.false Relation.Nullary.because Relation.Nullary.ofⁿ ¬p) , snd = {!!}
-- eqbStringrefl'' b | (.true Relation.Nullary.because Relation.Nullary.ofʸ refl) , snd rewrite snd = refl
-- eqbStringrefl'' b | (.false Relation.Nullary.because Relation.Nullary.ofⁿ ¬p) , snd = ⊥-elim (¬p refl)
最后一行是完整的证明。任何建议都会有所帮助!
通过导入定义了可判定性概念的Relation.Nullary
,您将获得yes
and no
patterns的访问权,而Agda会很高兴地加糖yes
为no
另一个为(.true Relation.Nullary.because Relation.Nullary.ofʸ refl)
。
关于目标的类型,它来自以下事实:字符串的相等性是通过字符列表上的按点相等来获得的,而字符的相等性是通过它们的基本表示形式为数字来获得的。这有点罗word,但这为我们提供了一个由Agda认可的安全且相当有效的定义。