coq 中 match 中参数结构属性的证明
Proofs of structural properties of arguments in match in coq
我想在 coq 中编写一个安全的 zip 函数，它接受参数长度相等作为参数。
Fixpoint zip {b a:Type} (proof : length l1 = length l2) (l1 : list a) (l2 : list b) : list (a * b) :=
match l1,l2 with
| nil,nil => nil
| cons a a',cons b b' => cons (a,b) (zip a' b')
| _,_ => (* never reached *)
end.
解决这类问题的一般方法是什么？我非常感谢有关在 coq 函数的上下文中使用优化类型的评论和资源。
在我看来，这是解决这个特定问题的最佳方法：
Require Import Coq.Lists.List.
Import ListNotations.
Fixpoint zip_pre {A B} (xs : list A) (ys : list B) : list (A * B) :=
match xs, ys with
| x :: xs, y :: ys => (x, y) :: zip_pre xs ys
| _, _ => []
end.
Definition zip {A B} (xs : list A) (ys : list B) (_ : length xs = length ys) :=
zip_pre xs ys.
换句话说，我们首先定义了一个不关心长度的 zip 版本，然后我们使用它来定义您要查找的函数。
这可能感觉像是在作弊；毕竟，zip 函数甚至没有使用它的证明参数！这是另一个可能更接近您最初寻找的版本：
Fixpoint zip' {A B} (xs : list A) (ys : list B) :
length xs = length ys -> list (A * B) :=
match xs, ys with
| x :: xs, y :: ys =>
fun H : S (length xs) = S (length ys) =>
(x, y) :: zip' xs ys ltac:(congruence)
| [], [] => fun _ => []
| x :: xs, [] => fun H : S (length xs) = 0 => ltac:(easy)
| [], y :: ys => fun H : 0 = S (length ys) => ltac:(easy)
end.
与zip不同，zip'以两种方式使用其证明参数。在矛盾的情况下，它调用一些策略代码（ltac:(easy)）来证明这种情况不会发生。在递归的情况下，需要找到 length xs = length ys 的证明才能应用递归调用；为此，它使用 congruence tacitc.
为什么 zip 比 zip' 好？它的代码更短，更易于阅读。特别要注意 zip' 如何匹配返回一个函数。每当我们需要细化模式匹配分支中的参数类型时，就需要使用这个习惯用法，称为 convoy 模式。实际上，zip' 比您想象的还要糟糕，因为履行证明义务的策略会生成代码。尝试打印 zip' 看看定义到底是什么样子！可悲的是，这种丑陋不仅仅是表面上的：这些更复杂的定义更难推理。例如，可以证明 zip 和 zip' 总是产生相同的输出。试试看有多好玩！
公平地说，有一些 Coq 插件可以更轻松地编写此类代码（例如 Equations 插件）。但最终他们仍会生成等同于 zip' 的代码。在这种情况下，长度假设对我们来说意义不大。
一般来说，最好避免 Coq 中的依赖类型，除非有强有力的论据证明额外的复杂性是合理的。例如，在 zip 的情况下，假设您有一些代码使用许多相同长度的不同列表 n。你可能想争辩说 zip 有一个倒数：
let xys := zip xs ys in
(map fst xys, map snd xys) = (xs, ys)
除非我们知道xs和ys的长度相同，否则无法证明这个结果。我们可以在我们的引理中添加一个额外的假设， 或 我们可以使用长度索引列表。这是一种可能的定义：
Definition vec A n := {l : list A | length l = n}.
{.. | ..} 是 Coq 的细化符号或子集类型。然后我们可以将一些函数重新打包到列表上以在 vec 上工作。例如，我们可以证明 map 需要 vec A n 到 vec B n。如果您不使用许多需要更改长度索引 n 的函数，则此方法会有所回报，因为在这些情况下，您需要推理类型上复杂长度表达式的相等性，而 Coq 不是很好在。特别是对于 vec，我建议您查看 mathcomp 的 tuple 库（可用 here），它提供了如何大规模使用此模式的一个很好的示例.
编辑
我想在 coq 中编写一个安全的 zip 函数，它接受参数长度相等作为参数。
Fixpoint zip {b a:Type} (proof : length l1 = length l2) (l1 : list a) (l2 : list b) : list (a * b) :=
match l1,l2 with
| nil,nil => nil
| cons a a',cons b b' => cons (a,b) (zip a' b')
| _,_ => (* never reached *)
end.
解决这类问题的一般方法是什么？我非常感谢有关在 coq 函数的上下文中使用优化类型的评论和资源。
在我看来，这是解决这个特定问题的最佳方法：
Require Import Coq.Lists.List.
Import ListNotations.
Fixpoint zip_pre {A B} (xs : list A) (ys : list B) : list (A * B) :=
match xs, ys with
| x :: xs, y :: ys => (x, y) :: zip_pre xs ys
| _, _ => []
end.
Definition zip {A B} (xs : list A) (ys : list B) (_ : length xs = length ys) :=
zip_pre xs ys.
换句话说，我们首先定义了一个不关心长度的 zip 版本，然后我们使用它来定义您要查找的函数。
这可能感觉像是在作弊；毕竟，zip 函数甚至没有使用它的证明参数！这是另一个可能更接近您最初寻找的版本：
Fixpoint zip' {A B} (xs : list A) (ys : list B) :
length xs = length ys -> list (A * B) :=
match xs, ys with
| x :: xs, y :: ys =>
fun H : S (length xs) = S (length ys) =>
(x, y) :: zip' xs ys ltac:(congruence)
| [], [] => fun _ => []
| x :: xs, [] => fun H : S (length xs) = 0 => ltac:(easy)
| [], y :: ys => fun H : 0 = S (length ys) => ltac:(easy)
end.
与zip不同，zip'以两种方式使用其证明参数。在矛盾的情况下，它调用一些策略代码（ltac:(easy)）来证明这种情况不会发生。在递归的情况下，需要找到 length xs = length ys 的证明才能应用递归调用；为此，它使用 congruence tacitc.
为什么 zip 比 zip' 好？它的代码更短，更易于阅读。特别要注意 zip' 如何匹配返回一个函数。每当我们需要细化模式匹配分支中的参数类型时，就需要使用这个习惯用法，称为 convoy 模式。实际上，zip' 比您想象的还要糟糕，因为履行证明义务的策略会生成代码。尝试打印 zip' 看看定义到底是什么样子！可悲的是，这种丑陋不仅仅是表面上的：这些更复杂的定义更难推理。例如，可以证明 zip 和 zip' 总是产生相同的输出。试试看有多好玩！
公平地说，有一些 Coq 插件可以更轻松地编写此类代码（例如 Equations 插件）。但最终他们仍会生成等同于 zip' 的代码。在这种情况下，长度假设对我们来说意义不大。
一般来说，最好避免 Coq 中的依赖类型，除非有强有力的论据证明额外的复杂性是合理的。例如，在 zip 的情况下，假设您有一些代码使用许多相同长度的不同列表 n。你可能想争辩说 zip 有一个倒数：
let xys := zip xs ys in
(map fst xys, map snd xys) = (xs, ys)
除非我们知道xs和ys的长度相同，否则无法证明这个结果。我们可以在我们的引理中添加一个额外的假设， 或 我们可以使用长度索引列表。这是一种可能的定义：
Definition vec A n := {l : list A | length l = n}.
{.. | ..} 是 Coq 的细化符号或子集类型。然后我们可以将一些函数重新打包到列表上以在 vec 上工作。例如，我们可以证明 map 需要 vec A n 到 vec B n。如果您不使用许多需要更改长度索引 n 的函数，则此方法会有所回报，因为在这些情况下，您需要推理类型上复杂长度表达式的相等性，而 Coq 不是很好在。特别是对于 vec，我建议您查看 mathcomp 的 tuple 库（可用 here），它提供了如何大规模使用此模式的一个很好的示例.
编辑