How to do induction on BinNums.Z in Coq/

user_652528 0
Viewed 170

I'm trying to do a simple function that like this

Fixpoint find_0 (n : BinNums.Z) :=
  match n with
    Z0 => n
  | Zpos p => find_0 p
  | Zneg q => find_0 q
  end.

But p is positive and not Z so this is ill typed.

If I try

Fixpoint find_0 (n : BinNums.Z) :=
  match n with
    Z0 => n
  | Zpos p => find_0 (n - 1)
  | Zneg q => find_0 (n + 1)
  end.

then Coq can't verify that this is strong normalizing, the error

Recursive definition of find_0 is ill-formed.
In environment
find_0 : BinNums.Z -> BinNums.Z
n : BinNums.Z
p : positive
Recursive call to find_0 has principal argument equal to 
"n - 1" instead of a subterm of "n".
Recursive definition is:
"fun n : BinNums.Z =>
 match n with
 | 0 => n
 | Z.pos _ => find_0 (n - 1)
 | BinInt.Z.neg _ => find_0 (n + 1)%Z
 end".

What to do in this situation?

Regards

coq
2 Answers

Since the definition of Bignums.Z:

Inductive Z : Set :=
    Z0 : Z
  | Zpos : positive -> Z
  | Zneg : positive -> Z.

is not recursive, you cannot write recursive functions over it. Instead you write a simple non recursive Definition to handle the constructors of Bignums.Z and there you call recursive functions you define on positives. It is also good style to define the functions you need on positives separataely on positives.

user_143149440

Every recursive function in Coq must clearly have a decreasing aspect. For many inductive types, this decreasing aspect is provided naturally by the recursive structure of this inductive type. If you look at the definition of positive, you see this:

Inductive positive : Set :=
xI : positive -> positive | xO : positive -> positive | xH : positive.

When an object p of type positive fits the pattern xO q, q is visibly smaller than p, if only as a piece of data (and here because the agreed meaning of xO is multiplication by 2, q is also numerically smaller than p).

When looking at the data type for Z, you see that there is no recursion and thus no visible decreasing pattern, where the smaller object would also be of type Z, so you cannot write a recursive function using the Fixpoint approach.

However, there exists an extension of Coq, called Equations, that will make it possible to write the function you want. The trick is that you still need to explain that something is decreasing during the recursive call. This calls for an extra object, a relation that is known to have no infinite path. Such a relation is called well-founded. Here the relation we will use is called Zwf.

From Equations Require Import Equations.
Require Import ZArith Zwf Lia.

#[export]Instance Zwf_wf (base : Z) : WellFounded (Zwf base).
Proof.
constructor; apply Zwf_well_founded.
Qed.

Equations find0 (x : Z) : Z by wf (Z.abs x) (Zwf 0) :=
  find0 Z0 := Z0; find0 (Zpos p) := find0 (Zpos p - 1);
  find0 (Zneg p) := find0 (Zneg p + 1).
Next Obligation.
set (x := Z.pos p); change (Zwf 0 (Z.abs (x - 1)) (Z.abs x)).
unfold Zwf. lia.
Qed.
Next Obligation.
set (x := Z.neg p); change (Zwf 0 (Z.abs (x + 1)) (Z.abs x)).
unfold Zwf. lia.
Qed.

There is a little more work than for a direct recursive function using Fixpoint, because we need to explain that we are using a well founded relation, make sure the Equations extension will find the information (this is the purpose of the Instance part of the script. Then, we also need to show that each recursive call satisfies the decrease property. Here, what decreases is the numeric value of the absolute value of the integer.

The Equations tool will gives you a collection of theorems to help reason on the find0 function. In particular, theorems find0_equation1, find0_equation2, and find0_equation3 really express that we defined a function that follows the algorithm you intended.

user_18092110
Related