如何在 Agda 中为 `Vec` 编写安全的 `length` 函数？

Question

因为我们有 Data.Vec，所以我们知道 Vec 是什么。

我想证明Nat和Vec ⊤是同构的

我已经成功创建了一个证明 Nat 可以转换为 Vec 的函数：

ℕ→vec : (n : ℕ) → Vec ⊤ n
ℕ→vec  zero   = []
ℕ→vec (suc a) = tt ∷ ℕ→vec a

当我试图写一个相应的 vec→ℕ 时，我失败了。

我想写这样的东西（不能编译但可读）：

vec→ℕ : ∀ {n} → Vec ⊤ n → (n : ℕ)
vec→ℕ  []      = zero
vec→ℕ (tt ∷ a) = suc (vec→ℕ a)

在第一段代码中，确保参数恰好是 return 值的长度。但是，如何确保第一个参数的长度恰好是 return 值？

Answer 1

我不知道这是否是最好的解决方案，但这是我想出来的。

open import Data.Vec
open import Data.Unit
open import Data.Nat
open import Data.Product

open import Relation.Binary.PropositionalEquality

vec→ℕ : ∀ {n} → Vec ⊤ n → ∃ (λ m → n ≡ m)
vec→ℕ  []      = zero , refl
vec→ℕ (tt ∷ a) with vec→ℕ a
vec→ℕ (tt ∷ a) | m , refl = suc m , refl

我没有说结果恰好是 n，而是引入了一个等式来指定这样的函数 return 和 m，这样 n ≡ m.希望对您有所帮助。使用您的类型签名，我遇到了一个解析错误并开发了这个。

Answer 2

您可以使 vec→ℕ 在定义上等于长度：

vec→ℕ : ∀ {n} → Vec ⊤ n → ℕ
vec→ℕ {n} _ = n

然后我认为这对 Agda 来说是足够透明的，在任何你需要属性的地方，你得到的 ℕ 是正确的，它会自动提供给你（即通过减少）。

编辑添加： 你可能认为这是未指定的，因为 vec→ℕ 的类型没有规定确切的 ℕ 自然 returns。然而，Agda 看穿了这个定义，所以例如如果需要，您可以证明以下外部正确性证明（但我认为它不会增加任何价值）：

open import Relation.Binary.PropositionalEquality

vec→ℕ-correct : ∀ {n} {xs : Vec ⊤ n} → vec→ℕ xs ≡ n
vec→ℕ-correct = refl

请注意，因为 vec→ℕ xs 在定义上等于 n，我们不需要在证明中查看 n 或 xs。

如何在 Agda 中为 `Vec` 编写安全的 `length` 函数？

How to write a safe `length` function to a `Vec` in Agda?

agda

dependent-type