提问人:fsuna064 提问时间:10/22/2020 最后编辑:fsuna064 更新时间:10/23/2020 访问量:78
Agda:使用“with”证明“Vec”“last”
Agda: proof about `Vec` `last` using `with`
问:
我试图证明以下说法
vecNat : ∀ {n} (xs : Vec ℕ n) → last (xs ∷ʳ 1) ≡ 1
但我对这个案子感到困惑。(x ∷ xs)
vecNat5 : ∀ {n} (xs : Vec ℕ n) → last (xs ∷ʳ 1) ≡ 1
vecNat5 [] = refl
vecNat5 (x ∷ xs) = {! 0!}
目标是
?0 : last ((x ∷ xs) ∷ʳ 1) ≡ 1
我首先尝试使用begin
vecNat5 : ∀ {n} (xs : Vec ℕ n) → last (xs ∷ʳ 1) ≡ 1
vecNat5 [] = refl
vecNat5 (x ∷ xs) =
begin
last ((x ∷ xs) ∷ʳ 1)
≡⟨⟩
1
∎
但随后出现此错误:
1 !=
(last (x ∷ (xs ∷ʳ 1))
| (initLast (x ∷ (xs ∷ʳ 1)) | initLast (xs ∷ʳ 1)))
of type ℕ
when checking that the expression 1 ∎ has type
last ((x ∷ xs) ∷ʳ 1) ≡ 1
所以我看了一下 in 的定义last
agda-stdlib/src/Data/Vec/Base.agda
last : ∀ {n} → Vec A (1 + n) → A
last xs with initLast xs
last .(ys ∷ʳ y) | (ys , y , refl) = y
并注意到该子句,所以以为我会尝试使用 .
我还在 https://agda.readthedocs.io/en/v2.6.1.1/language/with-abstraction.html?highlight=with#generalisation 中看到了一个使用证明(涉及)的例子。with
with
filter
with
所以我想尝试一下
vecNat : ∀ {n} (xs : Vec ℕ n) → last (xs ∷ʳ 1) ≡ 1
vecNat [] = refl
vecNat (x ∷ xs) with last (xs ∷ʳ 1)
... | r = {! 0!}
我得到作为目标:
?0 : (last (x ∷ (xs ∷ʳ 1))
| (initLast (x ∷ (xs ∷ʳ 1)) | initLast (xs ∷ʳ 1)))
≡ 1
我对如何前进感到困惑。还是我一开始就走错了方向?
谢谢!
编辑
当我尝试时
vecNat : ∀ {n} (xs : Vec ℕ n) → last (xs ∷ʳ 1) ≡ 1
vecNat [] = refl
vecNat (x ∷ xs) with initLast (xs ∷ʳ 1)
... | (xs , x , refl) = ?
我得到:
I'm not sure if there should be a case for the constructor refl,
because I get stuck when trying to solve the following unification
problems (inferred index ≟ expected index):
xs ∷ʳ 1 ≟ xs₁ ∷ʳ 1
when checking that the pattern refl has type xs ∷ʳ 1 ≡ xs₁ ∷ʳ 1
不太确定为什么现在有,为什么它不仅仅是xs₁
xs
答:
1赞
MrO
10/22/2020
#1
这是一个可能的解决方案,我将你的 1 改为 any ,并使向量的类型为泛型:a
一、部分进口:
module Vecnat where
open import Data.Nat
open import Data.Vec
open import Relation.Binary.PropositionalEquality
open import Data.Product
然后是一个简单但非常重要的属性,它指出在列表的头部添加元素不会更改其最后一个元素:
prop : ∀ {a} {A : Set a} {n x} (xs : Vec A (suc n)) → last (x ∷ xs) ≡ last xs
prop xs with initLast xs
... | _ , _ , refl = refl
最后,你要找的证明:
vecNat5 : ∀ {a} {A : Set a} {l n} (xs : Vec A n) → last (xs ∷ʳ l) ≡ l
vecNat5 [] = refl
vecNat5 (_ ∷ xs) = trans (prop (xs ∷ʳ _)) (vecNat5 xs)
评论