diff options
author | Stephane Glondu <steph@glondu.net> | 2010-07-21 09:46:51 +0200 |
---|---|---|
committer | Stephane Glondu <steph@glondu.net> | 2010-07-21 09:46:51 +0200 |
commit | 5b7eafd0f00a16d78f99a27f5c7d5a0de77dc7e6 (patch) | |
tree | 631ad791a7685edafeb1fb2e8faeedc8379318ae /plugins/subtac/test/euclid.v | |
parent | da178a880e3ace820b41d38b191d3785b82991f5 (diff) |
Imported Upstream snapshot 8.3~beta0+13298
Diffstat (limited to 'plugins/subtac/test/euclid.v')
-rw-r--r-- | plugins/subtac/test/euclid.v | 24 |
1 files changed, 24 insertions, 0 deletions
diff --git a/plugins/subtac/test/euclid.v b/plugins/subtac/test/euclid.v new file mode 100644 index 00000000..97c3d941 --- /dev/null +++ b/plugins/subtac/test/euclid.v @@ -0,0 +1,24 @@ +Require Import Coq.Program.Program. +Require Import Coq.Arith.Compare_dec. +Notation "( x & y )" := (existS _ x y) : core_scope. + +Require Import Omega. + +Program Fixpoint euclid (a : nat) (b : { b : nat | b <> O }) {wf lt a} : + { q : nat & { r : nat | a = b * q + r /\ r < b } } := + if le_lt_dec b a then let (q', r) := euclid (a - b) b in + (S q' & r) + else (O & a). + +Next Obligation. + assert(b * S q' = b * q' + b) by auto with arith ; omega. +Defined. + +Program Definition test_euclid : (prod nat nat) := let (q, r) := euclid 4 2 in (q, q). + +Eval lazy beta zeta delta iota in test_euclid. + +Program Definition testsig (a : nat) : { x : nat & { y : nat | x < y } } := + (a & S a). + +Check testsig. |