为什么 Coq 递归原则同时传递递归调用的子结构和结果？

Question

在检查了为不同的递归数据类型生成的一些不同的递归原则之后，我注意到在递归的情况下，子结构与对子结构的递归调用的结果一起传递。

例如，Print list_rect 给出：

list_rect =
fun (A : Type) (P : list A -> Type) (f : P nil)
  (f0 : forall (a : A) (l : list A), P l -> P (a :: l)%list) =>
fix F (l : list A) : P l :=
  match l as l0 return (P l0) with
  | nil => f
  | (y :: l0)%list => f0 y l0 (F l0)
  end
     : forall (A : Type) (P : list A -> Type),
       P nil ->
       (forall (a : A) (l : list A), P l -> P (a :: l)%list) ->
       forall l : list A, P l

在模式匹配中，cons case 看起来像 (y :: l0)%list => f0 y l0 (F l0)。为什么 f0 同时获取 l0 和在 l0 上递归调用 F 的结果？当您已经计算出调用 F 的结果时需要访问列表尾部的情况是什么？

Answer 1

只要你需要归纳假设，你就需要列表的尾部，因为它出现在它的类型中：写P l，l需要在范围内。

现在，如果您不关心类型，那么同时拥有列表的尾部和递归调用的一个很好的理由是效率：计算尾部与列表的大小成线性关系，但在途中抓住它是常数时间。当您只能访问迭代器而不能访问递归器时，此类问题的典型示例是 the definition of the predecessor function for unary natural numbers。

为什么 Coq 递归原则同时传递递归调用的子结构和结果？

Why do Coq recursion principles pass along both the substructure and the result of the recursive call?

coq