Coq：类型类与依赖记录

Question

我无法理解 Coq 中类型类和依赖记录之间的区别。参考手册给出了类型类的语法，但没有说明它们到底是什么以及应该如何使用它们。一些思考和搜索表明类型类本质上是依赖记录，带有一些语法糖，允许 Coq 自动推断一些隐式实例和参数。似乎当在任何给定的上下文中只有一个或多或少的可能实例时，类型类的算法似乎工作得更好，但这不是什么大问题，因为我们总是可以将类型类的所有字段移到它的参数中，从而消除歧义。此外，Instance 声明会自动添加到提示数据库中，这通常可以简化证明，但有时也会破坏它们，如果实例过于笼统并导致证明搜索循环或爆炸。还有其他我应该注意的问题吗？在两者之间进行选择的启发式是什么？例如。如果我只使用记录并尽可能将它们的实例设置为隐式参数，我会丢失任何东西吗？

Answer 1

你是对的：Coq 中的类型 classes 只是具有特殊管道和推理的记录（还有单一方法类型 classes 的特殊情况，但它实际上不是以任何方式影响这个答案）。因此，您选择类型 classes 而不是 "pure" 依赖记录的唯一原因是受益于您从它们获得的特殊推理：使用普通依赖记录的推理不是很强大并且不允许你省略了很多信息。

作为示例，请考虑以下代码，它定义了一个幺半群类型 class，并用自然数对其进行了实例化：

Class monoid A := Monoid {
  op : A -> A -> A;
  id : A;
  opA : forall x y z, op x (op y z) = op (op x y) z;
  idL : forall x, op id x = x;
  idR : forall x, op x id = x
}.

Require Import Arith.

Instance nat_plus_monoid : monoid nat := {|
  op := plus;
  id := 0;
  opA := plus_assoc;
  idL := plus_O_n;
  idR := fun n => eq_sym (plus_n_O n)
|}.

使用类型 class 推断，我们可以直接使用 nat 对任何幺半群起作用的任何定义，而无需提供类型 class 参数，例如

Definition times_3 (n : nat) := op n (op n n).

但是，如果通过将 Class 和 Instance 替换为 Record 和 Definition 将上述定义变成常规记录，则相同的定义将失败：

Toplevel input, characters 38-39: Error: In environment n : nat The term "n" has type "nat" while it is expected to have type  "monoid ?11".

类型 classes 的唯一警告是实例推理引擎有时会有点丢失，导致出现难以理解的错误消息。话虽这么说，考虑到这种可能性在那里甚至不可用，这并不是相对于依赖记录的劣势。

Coq：类型类与依赖记录

Coq: typeclasses vs dependent records

typeclass

coq