Coq 看不到两种类型是相同的

Question

我正在尝试在向量上定义 rev 函数，它的大小已嵌入其中，但我不知道如何在其上定义 rev 函数。

这是我的类型定义：

Inductive vect {X : Type} : nat -> Type -> Type
  := Nil  : vect 0 X
   | Cons : forall n, X -> vect n X -> vect (S n) X
.

我在上面定义了一些有用的函数：

Fixpoint app {X : Type} {n m : nat} (v1 : vect n X) (v2 : vect m X)
: vect (n + m) X :=
  match v1 with
    | Nil => v2
    | Cons _ x xs => Cons _ x (app xs v2)
  end.

Fixpoint fold_left {X Y : Type} {n : nat} (f : Y -> X -> Y) (acc : Y) (v : vect n X)
: Y :=
  match v with
    | Nil => acc
    | Cons _ x xs => fold_left f (f acc x) xs
  end.

现在，我想定义转速。我的第一个尝试是通过 fold_left，但结果完全失败了。

Fixpoint rev {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  fold_left (fun {X : Type} {k : nat} (acc : vect k X) (x : X) => x ::: acc) {{ }} v.

我不明白错误Error: The type of this term is a product while it is expected to be a sort.。

我的第二个尝试几乎不错，但 Coq 本身看不到“S n = (n + 1)”，我不知道如何告诉 Coq。

Fixpoint rev {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  match v in (vect n X) return (vect n X) with
    | Nil => Nil
    | Cons _ x xs => app (rev xs) {{ x }}
  end.

错误是The term "app (rev X n0 xs) {{x}}" has type "vect (n0 + 1) X" while it is expected to have type "vect (S n0) X"

如果您对 coq 代码有任何其他评论，请不要犹豫。

Answer 1

Fixpoint rev {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  fold_left (fun {X : Type} {k : nat} (acc : vect k X) (x : X) => Cons x acc) Nil v.

fold_left 的第一个显式参数必须具有 ?1 -> ?2 -> ?1 形式的类型，即两个参数的函数，其 return 类型与第一个参数相同。 [依赖]“product”是 Coq 函数的术语。您正在传递 fun (X:Type) b c d => … 形式的术语，因此 ?1 是 Type，并且术语 fun c d => …（显然具有产品类型）必须具有类型 ? 给定上下文，所以它必须具有类型 Type，即它必须是一个排序。

如果你尝试解决这个问题，你会发现你的 fold_left 函数在这里不起作用：你需要在迭代期间改变向量的长度，但是 [= 的迭代器参数16=] 具有在迭代期间保持不变的类型。使用您拥有的 fold_left 函数，如果您从累加器 Nil 开始，它是一个长度为 0 的向量，您最终将得到相同类型的结果，同样是一个长度向量0.

我还没有想过如何定义一个更通用的迭代器，让你定义 rev，但我相信这是可能的。

关于您的第二次尝试，vect (n0 + 1) X 和 vect (S n0) X 的问题在于它们不是同一类型，因为 n0 + 1 无法转换为 S n0。术语 n0 + 1 相等但不可转换，用作类型的术语只有在可转换时才可互换。

如果两种类型相等，您可以编写一个函数，将一种类型的术语“转换”为另一种类型的术语。事实上，执行此操作的一般函数是 eq_rect，相等类型族的析构函数。你可能会发现它定义了一个专门的函数来将一个向量转换为一个长度可证明但不一定可转换的向量。

Definition vect_eq_nat {X : Type} {m n : nat} (H : m = n) v :=
  eq_rect _ (fun k => @vect X k X) v _ H.

如果eq_rect的用法不能立即突出，你可以通过策略来定义这样的函数。只需确保您定义的函数不仅具有正确的类型，而且具有所需的结果，并使定义透明。

Definition vect_eq_nat {X : Type} {m n : nat} : m = n -> @vect X m X -> @vect X n X.
intros.
rewrite <- H.
exact X0.
Defined.
Print vect_eq_nat.

您还可以使用 Program 白话混合证明和术语。

Program Definition vect_plus_comm {X : Type} {n : nat} (v : @vect X (n+1) X) : @vect X (S n) X :=
  vect_eq_nat _ v.
Require Import Arith.
Require Import Omega.
Solve Obligation 0 using (intros; omega).

现在可以使用这个辅助定义来定义rev.

Fixpoint rev {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  match v in (vect n X) return (vect n X) with
    | Nil => Nil
    | Cons _ x xs => vect_plus_comm (app (rev xs) (Cons _ x Nil))
  end.

您可以使用 Program Fixpoint 直接定义 rev，一旦您完成了转换步骤。唯一的证明义务是 S n0 和 n0 + 1.

之间的相等性

Program Fixpoint rev' {X : Type} {n : nat} (v : @vect X n X) : @vect X n X :=
  match v in (vect n X) return (vect n X) with
    | Nil => Nil
    | Cons _ x xs => vect_eq_nat _ (app (rev' xs) (Cons _ x Nil))
  end.
Solve Obligation 0 using (intros; omega).

Coq 看不到两种类型是相同的

Coq can't see that two types are the same

types

functional-programming

coq