找到一个有根据的关系来证明在某个点停止减少的函数的终止

Question

假设我们有：

Require Import ZArith Program.

Program Fixpoint range (from to : Z) {measure f R} : list  :=
  if from <? to
  then from :: range (from + 1) to
  else [].

我想说服 Coq 这会终止 - 我尝试通过测量范围的大小作为 abs (to - from)。然而，这并不完全有效，因为一旦范围为空（即 from >= to），它就会再次开始增加。

我也试过测量：

Definition get_range (from to : Z) : option nat :=
  let range := (to - from) in 
    if (range <? 0)
    then None
    else Some (Z_to_nat (Z.abs range) (Z.abs_nonneg range)).

使用我的习惯：

Definition preceeds_eq (l r : option nat) : Prop :=
  match l, r with
    | None, None         => False
    | None, (Some _)     => True
    | (Some _), None     => False
    | (Some x), (Some y) => x < y
  end.

和演员：

Definition Z_to_nat (z : Z) (p : 0 <= z) : nat.
Proof.
  dependent destruction z.
    - exact (0%nat).
    - exact (Pos.to_nat p).
    - assert (Z.neg p < 0) by apply Zlt_neg_0.
      contradiction.
Defined.

但它遇到了我无法证明 None < None 和使用反身 preceeds_eq 使关系不成立的问题，这让我回到了同样的问题。

有没有办法让 Coq 相信 range 终止了？我的方法完全失效了吗？

Answer 1

如果您使用 Z.abs_nat 或 Z.to_nat 函数将间隔的长度映射到 nat，并使用一个函数来确定范围是否非空并提供更多信息输入 (Z_lt_dec) 然后解决方案变得非常简单：

Require Import ZArith Program.

Program Fixpoint range (from to : Z) {measure (Z.abs_nat (to - from))} : list Z :=
  if Z_lt_dec from to
  then from :: range (from + 1) to
  else [].
Next Obligation. apply Zabs_nat_lt; auto with zarith. Qed.

使用 Z_lt_dec 而不是它的布尔对应部分可以让您将 from < to 的证明传播到上下文中，从而使您能够轻松处理证明义务。

找到一个有根据的关系来证明在某个点停止减少的函数的终止

Finding a well founded relation to prove termination of a function that stops decreasing at some point

coq

termination

totality