删除 Coq 中大小列表的最后一个元素

Question

考虑以下大小列表的类型定义：

Inductive listn: nat -> Type -> Type :=
| nil: forall {A: Set}, listn 0 A
| cons: forall {n: nat} {A: Set}, A -> listn n A -> listn (S n) A.

这本质上是 Idris 中的 Vect 类型。

我正在尝试为 listn 定义 init 函数，它会删除最后一个元素。

我尝试的实现实际上与 Idris 中 init 的定义相同。这是在伊德里斯：

init : Vect (S len) elem -> Vect len elem
init (x::[])    = []
init (x::y::ys) = x :: init (y::ys)

转录成 Coq：

Fixpoint init {n: nat} {A: Set} (l: listn (S n) A): listn n A :=
match l with
| cons x nil => nil
| cons x (cons y ys) => cons x (init (cons y ys))
end.

…但这失败了：

The term "nil" has type "listn 0 ?A"
while it is expected to have type "listn ?n ?S@{a0:=S}"
(cannot unify "?n" and "0").

我认为 Coq 无法看出这种情况必然意味着 n 为零。这是我运行一直关注的问题 – Coq 无法看到 n 和列表本身之间的关系。

因此我的问题是：

如何在 Coq 中实现 init？
为什么 Idris 定义在 Idris 中有效，但在 Coq 中无效？ Idris 在幕后做了哪些 Coq 没有做的事情？

Answer 1

Coq 本身不太适合编写此类代码，但您可以使用 Equations plugin 使其更简单。尽管如此，让我们看看如何在没有外部依赖的情况下做到这一点：

Require Import Coq.Vectors.Vector.
(* Vector.t is equivalent to your listn type *)

Arguments nil {A}.
Arguments cons {A} _ {n}.

Fixpoint init {n: nat} {A: Set} (xs: Vector.t A (S n)): Vector.t A n :=
  match xs in Vector.t _ m return Vector.t A (pred m) with
  | nil => nil
  | cons x xs =>
      match xs in Vector.t _ m return Vector.t A m -> Vector.t A m with
      | nil      => fun _  => nil
      | cons _ _ => fun xs => cons x (init xs)
      end xs
  end.

此定义在某些方面与您的不同。首先，我们需要注释 match 的 return 类型，以解释它如何依赖于向量的长度。 in Vector.t _ m 部分表示 return 类型在向量的长度上是 generic —— 我们 cannot 假设长度的形式为 S n.

其次，我们必须枚举数据类型的所有情况：match 在 Coq 中总是详尽，即使某些分支由于键入而无法访问信息。因此，我在第一场比赛中加入了 nil 的情况。

第三，Coq 无法识别 init (cons y ys) 是有效的递归调用。我们通过在销毁它之前给 cons y ys 一个名字 xs 并使用 init xs 来解决这个问题。然而，有一个微妙之处。在cons x xs中，xs的类型是Vector.t A m for some m，可能是也可能不是后继者，所以我们不能直接调用 init。相反，我们首先析构 xs，然后仅在 cons 分支上执行递归调用。但是因为 match 在其长度参数上是通用的，Coq 看不到 match 内部和外部的 xs 长度之间的联系。解决方案是执行 Adam Chlipala 所说的 convoy 模式：我们使 match return 成为函数而不是普通向量，并将 xs 作为参数传递给外部比赛的。这样，两个长度之间的联系就不会丢失。

我对 Idris 了解不多，但我的猜测是它的 type-checking 算法比 Coq 的更复杂，这就是为什么它可以判断类似的定义是有效的。老实说，Coq 的规则非常简单（而且有限）。

删除 Coq 中大小列表的最后一个元素

Removing the last element of a sized list in Coq

coq