Imported Upstream version 8.2~rc2+dfsgupstream/8.2.rc2+dfsg

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).