Is it possible to "convert" a Fixpoint
definition for the count
function:
Fixpoint count (z: Z) (l: list Z) {struct l} : nat :=
match l with
| nil => 0%nat
| (z' :: l') => if (Z.eq_dec z z')
then S (count z l')
else count z l'
end.
To an Inductive
predicate (I have my first attempt bellow, but I'm not sure if it is correct)?
(This predicate is supposed to describe the relation between the function's input and output)
Inductive Count : nat -> list Z -> Z -> Prop :=
| CountNil : forall (z: Z), Count 0 nil z
| CountCons: forall (n: nat) (l0: list Z) (z: Z), Count n l0 z -> Count (S n) (cons z l0) z.
To find out if it's correct, I defined this Theorem (weak specification):
Theorem count_correct : forall (n: nat) (z: Z) (l: list Z), Count (count z l) l z.
Proof.
intros.
destruct l.
- constructor.
- ...
But I don't know how to complete it... Anyone can help?
Your relation is incorrect because it is missing the case for when the head of your list is not the
Z
you're looking for. E.g. there is no term of typeCount 0 [0] 1
even thoughcount 1 [0] = 0
. Add that, and while you're at it make the type more natural (order the arguments in the same way and also makez
a parameter).As for the correctness theorem, well,
count
is inductive onl
, so probably so should be any theorem about it.Do note that there's an automated mechanism to define
Count
andcount_correct
fromcount
: