减少依赖类型的参数

Question

在处理非依赖类型时，Coq（通常）会推断哪个参数在固定点中递减。但是，依赖类型并非如此。

例如，考虑以下示例，其中我有一个类型 A_list，它确保属性 P 对列表中的所有元素（类型 A）成立：

Require Import Coq.Lists.List.

Variable A: Type.
Variable P: A -> Prop.

Definition A_list := {a: list A | Forall P a}.

现在，假设我想要一个固定点递归地处理这样的列表（这里的 2 个引理并不有趣。dummy_arg 是模拟处理多个参数。）：

Lemma Forall_tl: forall P (h: A) t, Forall P (h::t) -> Forall P t.
Admitted.
Lemma aux: forall (l1: list A) l2 P, l1 = l2 -> Forall P l1 -> Forall P l2.
Admitted.

Fixpoint my_fixpoint (l: A_list) (dummy_arg: A) :=
match (proj1_sig l) as x return proj1_sig l = x -> bool with
| nil => fun _ => true
| hd::tl =>
    fun h =>
      my_fixpoint (exist (Forall P) tl (Forall_tl P hd tl (aux _ _ _ h (proj2_sig l)))) dummy_arg
end eq_refl.

正如预期的那样，returns 一个错误 "Cannot guess decreasing argument of fix." 因为，严格来说，我们并没有减少论点。尽管如此，我们显然在 proj1_sig l 上减少了（sig 中嵌入的列表）。

这可能可以使用 Program Fixpoints 解决，但是由于它一定是一种非常常见的模式来减少依赖类型的投影，我想知道 "right" 管理此类的方法是什么案例。

Answer 1

您可以使用我在中提到的方法之一解决此问题，包括 Program。如果你解耦列表和证明，那么它可以使用普通递归来完成：

Fixpoint my_fixpoint (l: list A) (pf : Forall P l) (dummy_arg: A) : bool :=
match l as x return Forall P x -> bool with
| nil => fun _ => true
| hd::tl => fun h => my_fixpoint tl (Forall_tl P hd tl h) dummy_arg
end pf.

减少依赖类型的参数

Decreasing argument with dependent types

coq

dependent-type

termination