summaryrefslogtreecommitdiff
path: root/theories/Classes/EquivDec.v
diff options
context:
space:
mode:
authorGravatar Stephane Glondu <steph@glondu.net>2009-02-01 00:54:40 +0100
committerGravatar Stephane Glondu <steph@glondu.net>2009-02-01 00:54:40 +0100
commitcfbfe13f5b515ae2e3c6cdd97e2ccee03bc26e56 (patch)
treeb7832bd5d412a5a5d69cb36ae2ded62c71124c22 /theories/Classes/EquivDec.v
parent113b703a695acbe31ac6dd6a8c4aa94f6fda7545 (diff)
Imported Upstream version 8.2~rc2+dfsgupstream/8.2.rc2+dfsg
Diffstat (limited to 'theories/Classes/EquivDec.v')
-rw-r--r--theories/Classes/EquivDec.v56
1 files changed, 25 insertions, 31 deletions
diff --git a/theories/Classes/EquivDec.v b/theories/Classes/EquivDec.v
index 1e58d05d..157217ae 100644
--- a/theories/Classes/EquivDec.v
+++ b/theories/Classes/EquivDec.v
@@ -1,4 +1,3 @@
-(* -*- coq-prog-args: ("-emacs-U" "-nois") -*- *)
(************************************************************************)
(* v * The Coq Proof Assistant / The Coq Development Team *)
(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
@@ -10,13 +9,12 @@
(* Decidable equivalences.
*
* Author: Matthieu Sozeau
- * Institution: LRI, CNRS UMR 8623 - UniversitĂcopyright Paris Sud
+ * Institution: LRI, CNRS UMR 8623 - UniversitÃcopyright Paris Sud
* 91405 Orsay, France *)
-(* $Id: EquivDec.v 11282 2008-07-28 11:51:53Z msozeau $ *)
+(* $Id: EquivDec.v 11800 2009-01-18 18:34:15Z msozeau $ *)
-Set Implicit Arguments.
-Unset Strict Implicit.
+Set Manual Implicit Arguments.
(** Export notations. *)
@@ -29,12 +27,12 @@ Require Import Coq.Logic.Decidable.
Open Scope equiv_scope.
-Class [ equiv : Equivalence A ] => DecidableEquivalence :=
+Class DecidableEquivalence `(equiv : Equivalence A) :=
setoid_decidable : forall x y : A, decidable (x === y).
(** The [EqDec] class gives a decision procedure for a particular setoid equality. *)
-Class [ equiv : Equivalence A ] => EqDec :=
+Class EqDec A R {equiv : Equivalence R} :=
equiv_dec : forall x y : A, { x === y } + { x =/= y }.
(** We define the [==] overloaded notation for deciding equality. It does not take precedence
@@ -54,7 +52,7 @@ Open Local Scope program_scope.
(** Invert the branches. *)
-Program Definition nequiv_dec [ EqDec A ] (x y : A) : { x =/= y } + { x === y } := swap_sumbool (x == y).
+Program Definition nequiv_dec `{EqDec A} (x y : A) : { x =/= y } + { x === y } := swap_sumbool (x == y).
(** Overloaded notation for inequality. *)
@@ -62,10 +60,10 @@ Infix "<>" := nequiv_dec (no associativity, at level 70) : equiv_scope.
(** Define boolean versions, losing the logical information. *)
-Definition equiv_decb [ EqDec A ] (x y : A) : bool :=
+Definition equiv_decb `{EqDec A} (x y : A) : bool :=
if x == y then true else false.
-Definition nequiv_decb [ EqDec A ] (x y : A) : bool :=
+Definition nequiv_decb `{EqDec A} (x y : A) : bool :=
negb (equiv_decb x y).
Infix "==b" := equiv_decb (no associativity, at level 70).
@@ -77,16 +75,13 @@ Require Import Coq.Arith.Peano_dec.
(** The equiv is burried inside the setoid, but we can recover it by specifying which setoid we're talking about. *)
-Program Instance nat_eq_eqdec : ! EqDec nat eq :=
- equiv_dec := eq_nat_dec.
+Program Instance nat_eq_eqdec : EqDec nat eq := eq_nat_dec.
Require Import Coq.Bool.Bool.
-Program Instance bool_eqdec : ! EqDec bool eq :=
- equiv_dec := bool_dec.
+Program Instance bool_eqdec : EqDec bool eq := bool_dec.
-Program Instance unit_eqdec : ! EqDec unit eq :=
- equiv_dec x y := in_left.
+Program Instance unit_eqdec : EqDec unit eq := λ x y, in_left.
Next Obligation.
Proof.
@@ -94,39 +89,38 @@ Program Instance unit_eqdec : ! EqDec unit eq :=
reflexivity.
Qed.
-Program Instance prod_eqdec [ EqDec A eq, EqDec B eq ] :
+Program Instance prod_eqdec `(EqDec A eq, EqDec B eq) :
! EqDec (prod A B) eq :=
- equiv_dec x y :=
+ { equiv_dec x y :=
let '(x1, x2) := x in
let '(y1, y2) := y in
if x1 == y1 then
if x2 == y2 then in_left
else in_right
- else in_right.
+ else in_right }.
Solve Obligations using unfold complement, equiv ; program_simpl.
-Program Instance sum_eqdec [ EqDec A eq, EqDec B eq ] :
- ! EqDec (sum A B) eq :=
+Program Instance sum_eqdec `(EqDec A eq, EqDec B eq) :
+ EqDec (sum A B) eq := {
equiv_dec x y :=
match x, y with
| inl a, inl b => if a == b then in_left else in_right
| inr a, inr b => if a == b then in_left else in_right
| inl _, inr _ | inr _, inl _ => in_right
- end.
+ end }.
Solve Obligations using unfold complement, equiv ; program_simpl.
-(** Objects of function spaces with countable domains like bool have decidable equality. *)
-
-Require Import Coq.Program.FunctionalExtensionality.
+(** Objects of function spaces with countable domains like bool have decidable equality.
+ Proving the reflection requires functional extensionality though. *)
-Program Instance bool_function_eqdec [ EqDec A eq ] : ! EqDec (bool -> A) eq :=
- equiv_dec f g :=
+Program Instance bool_function_eqdec `(EqDec A eq) : ! EqDec (bool -> A) eq :=
+ { equiv_dec f g :=
if f true == g true then
if f false == g false then in_left
else in_right
- else in_right.
+ else in_right }.
Solve Obligations using try red ; unfold equiv, complement ; program_simpl.
@@ -138,8 +132,8 @@ Program Instance bool_function_eqdec [ EqDec A eq ] : ! EqDec (bool -> A) eq :=
Require Import List.
-Program Instance list_eqdec [ eqa : EqDec A eq ] : ! EqDec (list A) eq :=
- equiv_dec :=
+Program Instance list_eqdec `(eqa : EqDec A eq) : ! EqDec (list A) eq :=
+ { equiv_dec :=
fix aux (x : list A) y { struct x } :=
match x, y with
| nil, nil => in_left
@@ -148,7 +142,7 @@ Program Instance list_eqdec [ eqa : EqDec A eq ] : ! EqDec (list A) eq :=
if aux tl tl' then in_left else in_right
else in_right
| _, _ => in_right
- end.
+ end }.
Solve Obligations using unfold equiv, complement in * ; program_simpl ; intuition (discriminate || eauto).