归纳类型和 nat 的相互递归

Question

考虑这个例子：

Inductive T :=
| foo : T
| bar : nat -> T -> T.

Fixpoint evalT (t:T) {struct t} : nat :=
  match t with
  | foo => 1
  | bar n x => evalBar x n
  end
with evalBar (x:T) (n:nat) {struct n} : nat :=
  match n with
  | O => 0
  | S n' => (evalT x) + (evalBar x n')
  end.

Coq 拒绝它并出现错误：递归调用 evalBar 的主要参数等于 "n" 而不是 "x"。

我知道终止检查器被两个不相关的归纳类型（T 和 nat）弄糊涂了。但是，看起来我试图定义的函数确实会终止。我怎样才能让 Coq 接受它？

Answer 1

我找到的一个解决方案是使用 nat_rec 而不是 evalBar:

Fixpoint evalT (t:T) {struct t} : nat :=
  match t with
  | foo => 1
  | bar n x => @nat_rec _ 0 (fun n' t' => (evalT x) + t') n
  end.

它有效，但我希望我可以将 nat_rec 隐藏在 evalBar 定义下以隐藏详细信息。在我的实际项目中，这种构造被多次使用。

Answer 2

另一种解决方案是使用嵌套固定点。

Fixpoint evalT (t:T) {struct t} : nat :=
  match t with
  | foo => 1
  | bar n x => let fix evalBar n {struct n} :=
                 match n with
                 | 0 => 0
                 | S n' => Nat.add (evalT x) (evalBar n')
                 end
               in evalBar n
  end.

重点是从 evalBar 中删除参数 x。因此，对 evalT 的递归调用是在 bar n x 的 x 上完成的，而不是作为 evalBar 的参数给出的 x，因此终止检查器可以验证 evalT.

的定义

这与在另一个答案中提出的 nat_rec 版本的想法相同。

归纳类型和 nat 的相互递归

mutual recursion on an inductive type and nat

recursion

coq

termination