在 coq 中使用哪个矢量库？

Question

我想知道，在 coq 中是否有一个常用的向量库，即按类型长度索引的列表。

一些教程引用了 Bvector，但是我尝试导入时没有找到它。

有 Coq.Vectors.Vectordef，但那里定义的类型只是命名为 t，这让我认为它是供内部使用的。

对于不想推出自己的库的人来说，最好或最常见的做法是什么？我对标准库中的向量有误吗？还是我缺少另一个 Lib？还是人们只是使用列表，并配以长度证明？

Answer 1

在 Coq 中通常有三种处理向量的方法，每种方法都有自己的权衡：

归纳定义的向量，由 Coq 标准库提供。
列表与它们的长度断言配对。
递归嵌套元组。

带长度的列表很好，因为它们很容易被强制转换为列表，因此您可以重用许多在普通列表上运行的函数。归纳向量的缺点是需要大量依赖类型的模式匹配，这取决于你用它们做什么。

对于大多数开发，我更喜欢递归元组定义：

Definition Vec : nat -> Type :=
  fix vec n := match n return Type with
               | O   => unit
               | S n => prod A (vec n)
               end.

Answer 2

我在 Coq 中广泛使用向量，我使用的是标准 Coq.Vectors.Vector 模块。它使用教科书归纳向量定义。

这种方法的主要问题是，在长度向量（例如 a+b 和 b+a 不是同一类型的情况下，它需要进行繁琐的类型转换。

我还最终使用了 Coq CoLoR 库 (opam instal coq-color)，其中包含包 CoLoR.Util.Vector.VecUtil，其中包含许多有用的引理和向量定义。我最后在上面写了更多。

在 coq 中使用哪个矢量库？

Which vector library to use in coq?

list

vector

coq

proof

dependent-type