diff options
author | jadep <jade.philipoom@gmail.com> | 2016-08-25 12:58:28 -0400 |
---|---|---|
committer | jadep <jade.philipoom@gmail.com> | 2016-08-31 10:03:57 -0400 |
commit | 2dd91e595de85e82be1b88606ee4368a16f1709d (patch) | |
tree | 4beea62979d5d19eb3a348fdf5d285a7e5ab9f52 /src/Util/Tuple.v | |
parent | 203b50277568b8e5574d85e9ae13b61918187d6a (diff) |
Defined an equality comparison for tuples that uses bool instead of Prop (like Z.eqb). This is necessary for the runtime equality comparison on tuples that will appear in square root calculations during point-decoding.
Diffstat (limited to 'src/Util/Tuple.v')
-rw-r--r-- | src/Util/Tuple.v | 40 |
1 files changed, 40 insertions, 0 deletions
diff --git a/src/Util/Tuple.v b/src/Util/Tuple.v index 968eb99ad..568c3ce21 100644 --- a/src/Util/Tuple.v +++ b/src/Util/Tuple.v @@ -145,6 +145,46 @@ Proof. destruct n; unfold fieldwise; exact _. Qed. +Fixpoint fieldwiseb' {A B} (n:nat) (R:A->B->bool) (a:tuple' A n) (b:tuple' B n) {struct n} : bool. + destruct n; simpl @tuple' in *. + { exact (R a b). } + { exact (R (snd a) (snd b) && fieldwiseb' _ _ n R (fst a) (fst b))%bool. } +Defined. + +Definition fieldwiseb {A B} (n:nat) (R:A->B->bool) (a:tuple A n) (b:tuple B n) : bool. + destruct n; simpl @tuple in *. + { exact true. } + { exact (fieldwiseb' _ R a b). } +Defined. + +Arguments fieldwiseb' {A B n} _ _ _. +Arguments fieldwiseb {A B n} _ _ _. + +Lemma fieldwiseb'_fieldwise' :forall {A B} n R Rb + (a:tuple' A n) (b:tuple' B n), + (forall a b, Rb a b = true <-> R a b) -> + (fieldwiseb' Rb a b = true <-> fieldwise' R a b). +Proof. + intros. + revert n a b; + induction n; intros; simpl @tuple' in *; + simpl fieldwiseb'; simpl fieldwise'; auto. + cbv beta. + rewrite Bool.andb_true_iff. + f_equiv; auto. +Qed. + +Lemma fieldwiseb_fieldwise :forall {A B} n R Rb + (a:tuple A n) (b:tuple B n), + (forall a b, Rb a b = true <-> R a b) -> + (fieldwiseb Rb a b = true <-> fieldwise R a b). +Proof. + intros; destruct n; simpl @tuple in *; + simpl @fieldwiseb; simpl @fieldwise; try tauto. + auto using fieldwiseb'_fieldwise'. +Qed. + + Fixpoint from_list_default' {T} (d y:T) (n:nat) (xs:list T) : tuple' T n := match n return tuple' T n with | 0 => y (* ignore high digits *) |