← Back to branch summary

~ubuntu-branches/ubuntu/wily/coq-doc/wily

« back to all changes in this revision

Viewing changes to theories/Classes/SetoidDec.v

  • Committer: Bazaar Package Importer
  • Author(s): Stéphane Glondu, Stéphane Glondu, Samuel Mimram
  • Date: 2010-01-07 22:50:39 UTC
  • mfrom: (1.2.2 upstream)
  • Revision ID: james.westby@ubuntu.com-20100107225039-n3cq82589u0qt0s2
Tags: 8.2pl1-1
http://bugs.debian.org/563669
http://bugs.debian.org/543545
[ Stéphane Glondu ]
* New upstream release (Closes: #563669)
  - remove patches
* Packaging overhaul:
  - use git, advertise it in Vcs-* fields of debian/control
  - use debhelper 7 and dh with override
  - use source format 3.0 (quilt)
* debian/control:
  - set Maintainer to d-o-m, set Uploaders to Sam and myself
  - add Homepage field
  - bump Standards-Version to 3.8.3
* Register PDF documentation into doc-base
* Add debian/watch
* Update debian/copyright

[ Samuel Mimram ]
* Change coq-doc's description to mention that it provides documentation in
  pdf format, not postscript, closes: #543545.

Show diffs side-by-side

added added

removed removed

Lines of Context:
theories/Classes/SetoidDec.v
 
1
(************************************************************************)
 
2
(*  v      *   The Coq Proof Assistant  /  The Coq Development Team     *)
 
3
(* <O___,, * CNRS-Ecole Polytechnique-INRIA Futurs-Universite Paris Sud *)
 
4
(*   \VV/  **************************************************************)
 
5
(*    //   *      This file is distributed under the terms of the       *)
 
6
(*         *       GNU Lesser General Public License Version 2.1        *)
 
7
(************************************************************************)
 
8
 
 
9
(* Decidable setoid equality theory.
 
10
 *
 
11
 * Author: Matthieu Sozeau
 
12
 * Institution: LRI, CNRS UMR 8623 - UniversitÃcopyright Paris Sud
 
13
 *              91405 Orsay, France *)
 
14
 
 
15
(* $Id: SetoidDec.v 11800 2009-01-18 18:34:15Z msozeau $ *)
 
16
 
 
17
Set Implicit Arguments.
 
18
Unset Strict Implicit.
 
19
 
 
20
(** Export notations. *)
 
21
 
 
22
Require Export Coq.Classes.SetoidClass.
 
23
 
 
24
(** The [DecidableSetoid] class asserts decidability of a [Setoid]. It can be useful in proofs to reason more 
 
25
   classically. *)
 
26
 
 
27
Require Import Coq.Logic.Decidable.
 
28
 
 
29
Class DecidableSetoid `(S : Setoid A) :=
 
30
  setoid_decidable : forall x y : A, decidable (x == y).
 
31
 
 
32
(** The [EqDec] class gives a decision procedure for a particular setoid equality. *)
 
33
 
 
34
Class EqDec `(S : Setoid A) :=
 
35
  equiv_dec : forall x y : A, { x == y } + { x =/= y }.
 
36
 
 
37
(** We define the [==] overloaded notation for deciding equality. It does not take precedence
 
38
   of [==] defined in the type scope, hence we can have both at the same time. *)
 
39
 
 
40
Notation " x == y " := (equiv_dec (x :>) (y :>)) (no associativity, at level 70).
 
41
 
 
42
Definition swap_sumbool {A B} (x : { A } + { B }) : { B } + { A } :=
 
43
  match x with
 
44
    | left H => @right _ _ H 
 
45
    | right H => @left _ _ H 
 
46
  end.
 
47
 
 
48
Require Import Coq.Program.Program.
 
49
 
 
50
Open Local Scope program_scope.
 
51
 
 
52
(** Invert the branches. *)
 
53
 
 
54
Program Definition nequiv_dec `{EqDec A} (x y : A) : { x =/= y } + { x == y } := swap_sumbool (x == y).
 
55
 
 
56
(** Overloaded notation for inequality. *)
 
57
 
 
58
Infix "=/=" := nequiv_dec (no associativity, at level 70).
 
59
 
 
60
(** Define boolean versions, losing the logical information. *)
 
61
 
 
62
Definition equiv_decb `{EqDec A} (x y : A) : bool :=
 
63
  if x == y then true else false.
 
64
 
 
65
Definition nequiv_decb `{EqDec A} (x y : A) : bool :=
 
66
  negb (equiv_decb x y).
 
67
 
 
68
Infix "==b" := equiv_decb (no associativity, at level 70).
 
69
Infix "<>b" := nequiv_decb (no associativity, at level 70).
 
70
 
 
71
(** Decidable leibniz equality instances. *)
 
72
 
 
73
Require Import Coq.Arith.Arith.
 
74
 
 
75
(** The equiv is burried inside the setoid, but we can recover it by specifying which setoid we're talking about. *)
 
76
 
 
77
Program Instance eq_setoid A : Setoid A | 10 :=
 
78
  { equiv := eq ; setoid_equiv := eq_equivalence }.
 
79
 
 
80
Program Instance nat_eq_eqdec : EqDec (eq_setoid nat) :=
 
81
  eq_nat_dec.
 
82
 
 
83
Require Import Coq.Bool.Bool.
 
84
 
 
85
Program Instance bool_eqdec : EqDec (eq_setoid bool) :=
 
86
  bool_dec.
 
87
 
 
88
Program Instance unit_eqdec : EqDec (eq_setoid unit) :=
 
89
  λ x y, in_left.
 
90
 
 
91
  Next Obligation.
 
92
  Proof.
 
93
    destruct x ; destruct y.
 
94
    reflexivity.
 
95
  Qed.
 
96
 
 
97
Program Instance prod_eqdec `(! EqDec (eq_setoid A), ! EqDec (eq_setoid B)) : EqDec (eq_setoid (prod A B)) :=
 
98
  λ x y,
 
99
    let '(x1, x2) := x in 
 
100
    let '(y1, y2) := y in 
 
101
    if x1 == y1 then 
 
102
      if x2 == y2 then in_left
 
103
      else in_right
 
104
    else in_right.
 
105
 
 
106
  Solve Obligations using unfold complement ; program_simpl.
 
107
 
 
108
(** Objects of function spaces with countable domains like bool have decidable equality. *)
 
109
 
 
110
Program Instance bool_function_eqdec `(! EqDec (eq_setoid A)) : EqDec (eq_setoid (bool -> A)) :=
 
111
  λ f g,
 
112
    if f true == g true then
 
113
      if f false == g false then in_left
 
114
      else in_right
 
115
    else in_right.
 
116
 
 
117
  Solve Obligations using try red ; unfold equiv, complement ; program_simpl.
 
118
 
 
119
  Next Obligation.
 
120
  Proof.
 
121
    extensionality x.
 
122
    destruct x ; auto.
 
123
  Qed.