2

我一直在尝试互感类型，并决定定义自然数和向量的互感版本（列表及其类型中的大小）。我将它们和无限数定义为：

CoInductive conat : Set :=
| cozero : conat
| cosuc : conat -> conat.

CoInductive covec (A : Set) : conat -> Set :=
| conil : covec A cozero
| cocons : forall (n : conat), A -> covec A n -> covec A (cosuc n).           

CoFixpoint infnum : conat := cosuc infnum.

除了我为无限协向量给出的定义之外，这一切都有效

CoFixpoint ones : covec nat infnum := cocons 1 ones.

这给出了以下类型不匹配

Error:
In environment
ones : covec nat infnum
The term "cocons 1 ones" has type "covec nat (cosuc infnum)" while it is expected to have type
 "covec nat infnum".

我认为编译器会接受这个定义，因为根据定义，infnum = cosuc infnum。如何让编译器理解这些表达式是相同的？

4

1 回答 1

1

Adam Chlipala 的 CPDT 中描述了解决这个问题的标准方法（参见Coinduction章节）。

Definition frob (c : conat) :=
  match c with
  | cozero => cozero
  | cosuc c' => cosuc c'
  end.

Lemma frob_eq (c : conat) : c = frob c.
Proof. now destruct c. Qed.

您可以像这样使用上述定义：

CoFixpoint ones : covec nat infnum.
Proof. rewrite frob_eq; exact (cocons 1 ones). Defined.

或者，也许，以更易读的方式：

Require Import Coq.Program.Tactics.

Program CoFixpoint ones : covec nat infnum := cocons 1 ones.
Next Obligation. now rewrite frob_eq. Qed.
于 2017-10-14T07:20:52.047 回答