定义产品类型的递归函数

Question

我试图将每个整数形式化为自然数对的等价 class，其中第一个分量是正数部分，第二个分量是负数部分。

Definition integer : Type := prod nat nat.

我想定义一个正负尽可能抵消的归一化函数。

Fixpoint normalize (i : integer) : integer :=
let (a, b) := i in
match a with
| 0 => (0, b)
| S a' => match b with
        | 0 => (S a', 0)
        | S b' => normalize (a', b')
        end
end.

但是 Coq 说：

Error: Recursive definition of normalize is ill-formed. In environment normalize : integer -> integer i : integer a : nat b : nat a' : nat b' : nat Recursive call to normalize has principal argument equal to "(a', b')" instead of a subterm of "i".

我认为这可能与有根据的递归有关？

Answer 1

必须对原始参数的 "subterm" 进行递归调用。归纳类型中术语的子术语本质上是与用于创建原始术语的类型相同的术语。例如，像 S a' 这样的自然数的子项是 a'.

不幸的是，对于您的定义（如所写），一对 i: prod nat nat 在这个意义上没有任何子项。这是因为 prod 不是递归类型。它的构造函数 pair: A -> B -> prod A B 不接受任何类型 prod A B 作为参数。

要解决此问题，我建议您先在两个单独的自然数上定义函数。

Fixpoint normalize_helper (a b : nat) : integer :=
match a with
| 0 => (0, b)
| S a' => match b with
        | 0 => (S a', 0)
        | S b' => normalize a' b'
        end
end.

那么normalize可以很容易地定义为normalize_helper。

Answer 2

现在 Program Fixpoint 已经变得很好了，你可以这样定义 normalize:

Require Import Program.

Definition integer :Type := (nat*nat).

Program Fixpoint normalize (i:integer) {measure (max (fst i) (snd i))} :=
  match i with
  | (S i1, S i2) => normalize (i1, i2)
  | (_, _) => i
  end.

它可以自己处理所有的证明义务！

要使用它并对其进行推理，您可能需要定义一些重写引理。

Lemma normalize_0_l i: normalize (0, i) = (0, i).
Proof. reflexivity. Qed.

Lemma normalize_0_r i: normalize (i, 0) = (i, 0).
Proof. destruct i; reflexivity. Qed.

Lemma normalize_inj i j: normalize (S i, S j) = normalize (i, j).
  unfold normalize at 1; rewrite fix_sub_eq; simpl; fold (normalize (i, j)).
  - reflexivity.
  - now intros [[|x] [|y]] f g H.
Qed.

我从获得了 unfold... rewrite ... simpl... fold 技巧！

Answer 3

除了@larsr 的回答：Equations 插件提供了一些不错的功能，例如自动生成类似于 normalize_0_l 的简化引理等。对于下面的示例，我们有 normalize_equation_1、normalize_equation_2 等。此外，正如 Function 插件所做的那样，Equations 提供了函数归纳方案，可以非常优雅地证明函数的属性。

From Equations Require Import Equations.

Definition integer : Type := prod nat nat.

Equations normalize (i : integer) : integer by wf (fst i) :=
normalize (0, b) := (0, b);
normalize (S a', 0) := (S a', 0);
normalize (S a', S b') := normalize (a', b')
.
(* see Coq's response for the list of auto generated lemmas *)

让我们用函数归纳来证明 normalize 的一些性质。方程式提供了一些使使用它更容易的策略。在这种情况下，我将使用 funelim。

From Coq Require Import Arith.

Lemma normalize_sub_lt a b :
  a < b -> normalize (a, b) = (0, b - a).
Proof.
  funelim (normalize (a, b)); simpl in *.
  - now rewrite Nat.sub_0_r.
  - now intros []%Nat.nlt_0_r.
  - intros a_lt_b%Nat.succ_lt_mono; auto.
Qed.

normalize的规范的第二部分可以用同样的方式证明。

Lemma normalize_sub_gte a b :
  b <= a -> normalize (a, b) = (a - b, 0).

Answer 4

虽然学习如何编写这种类型的递归函数很有用，但在这种特殊情况下，我认为最好避免递归并使用标准定义：

Require Import Coq.Arith.Arith.

Definition integer : Type := (nat * nat).

Definition normalize (i : integer) : integer :=
  if snd i <=? fst i then (fst i - snd i, 0)
  else (0, snd i - fst i).

定义产品类型的递归函数

Defining recursive function over product type

coq

termination

totality