Coq：依赖列表上的类型不匹配可以通过证明来解决

Question

在我最后一次使用 coq 中的列表时，我遇到了一个类型问题。但首先是定义；

休闲列表：

Inductive list (a : Set) : Set :=
| nil : list a
| cons : a -> list a -> list a
.

Fixpoint len {a : Set} (l : list a) : nat :=
  match l with
  | nil _ => 0
  | cons _ _ t => 1 + (len t)
  end.

家属名单：

Inductive dlist (a : Set) : nat -> Set :=
| dnil : dlist a 0
| dcons : a -> forall n, dlist a n -> dlist a (S n)
.

转化次数：

Fixpoint from_d {a : Set} {n : nat} (l : dlist a n) : list a :=
  match l with
  | dnil _ => nil _
  | dcons _ h _ t => cons _ h (from_d t)
  end.

Fixpoint to_d {a : Set} (l : list a) : dlist a (len l) :=
  match l with
  | nil _ => dnil _
  | cons _ h t => dcons _ h _ (to_d t)
  end.

我想证明转换回旋处，严格来说

Theorem d_round : forall (a : Set) (n : nat) (l : dlist a n),
    to_d (from_d l) = l.

但是我得到以下错误：

The term "l" has type "dlist a n" while it is expected to have type
 "dlist a (len (from_d l))".

这很容易理解，但我完全不知道如何解决它。我可以很容易地证明

forall (a : Set) (n : nat) (l : dlist a n), n = len (from_d l).

但我看不出有什么方法可以使用这个定理来说服 Coq 列表的长度保持不变。怎么做？

Answer 1

你要证明的是异质等式，l和to_d (from_d l)的类型不同，无法与同质等式(=)进行比较。

如果理论是外延的，那将是另一回事（相同类型可以转换），但是您必须手动处理这种差异。一种方法是定义一些 transport，它对应于莱布尼茨原理：从 x = y 推导出任何 P.

的 P x -> P y

Definition transport {A} {x y : A} (e : x = y) {P : A -> Type} (t : P x) : P y :=
  match e with
  | eq_refl => t
  end.

在你的情况下它会是 n = m -> dlist A n -> dlist A m 所以你甚至可以使用专门的版本。

定理可以表述为：

Axiom e : forall (a : Set) (n : nat) (l : dlist a n), n = len (from_d l).

Theorem d_round : 
  forall (A : Set) (n : nat) (l : dlist A n),
    to_d (from_d l) = transport (e _ _ _) l.

现在你必须处理阻碍你前进的等式，但自然数上的等式是可判定的，因此是一个命题（n = m 的任何两个证明总是相等的，特别是 n = n 等于 eq_refl；与 transport eq_refl t = t).

完美结合的事实

Answer 2

传输（参见 Théo 的回答）确实是一个常见的解决方案。一种不太常见的方法是使用更直接的异构相等形式。使用从 Coq.Logic.Eqdep.

导入的 eq_dep 而不是同类 eq

陈述to_d (from_d l) : dlist a (len (from_d l))和l : dlist a n之间的等式：

找出两种类型的区别，在本例中是len (from_d l) vs n，它们的类型是nat;
找到围绕这些差异的共同上下文：dlist a（或fun n => dlist a n），即，将前面的术语映射到两侧各自类型的函数所需的方程式。
eq_dep的第一个参数是差异的类型（nat）；第二个参数是公共上下文（dlist a）；第三个参数是传递上下文以获取左侧类型的术语（可以将其称为 LHS 的 "type index"，len (from_d l)）；第四个参数是等式的左边；第五和第六类似地描述了右侧。

由此产生的定理比传输版本更强：它同时声明两个项及其类型索引的相等性，而传输需要证明类型索引（n = len (from_d l)）相等单独制作。此外，对于传输，等式证明将明确显示为最终等式定理的一项，而异构等式不会暴露此类多余数据。

该证明具有简单的结构（事实上，完全相同的脚本适用于简单列表的类似定理），但也隐藏了许多复杂性，但在执行此类证明时仍需要注意这些复杂性。强烈建议您熟悉相关模式匹配并对策略生成的证明项有所了解。

Require Import Coq.Logic.Eqdep.

(* "to_d (from_d l) = l" *)
Theorem d_round : forall (a : Set) (n : nat) (l : dlist a n),
    eq_dep _ (dlist a) _ (to_d (from_d l)) _ l.
(* In full: eq_dep nat (dlist a) (len (from_d l)) (to_d (from_d l)) n l *)
Proof.
  intros.
  induction l.
  - simpl.
    reflexivity.
  - simpl.
    rewrite IHl.
    reflexivity.
Qed.

Coq：依赖列表上的类型不匹配可以通过证明来解决

Coq: type mismatch on dependent lists which could be solved by a proof

list

theorem-proving

coq

dependent-type