Merge branch 'bug4725' into v8.5

1 files changed, 38 insertions, 0 deletions

diff --git a/test-suite/bugs/closed/4725.v b/test-suite/bugs/closed/4725.v
new file mode 100644
index 000000000..fd5e0fb60
--- /dev/null
+++ b/test-suite/bugs/closed/4725.v
@@ -0,0 +1,38 @@
+Require Import EquivDec Equivalence List Program.
+Require Import Relation_Definitions.
+Import ListNotations.
+Generalizable All Variables.
+
+Fixpoint removeV `{eqDecV : @EqDec V eqV equivV}`(x : V) (l : list V) : list V
+:=
+  match l with
+  | nil => nil
+  | y::tl => if (equiv_dec x y) then removeV x tl else y::(removeV x tl)
+  end.
+
+Lemma remove_le {V:Type}{eqV:relation V}{equivV:@Equivalence V eqV}{eqDecV :
+@EqDec V eqV equivV} (xs : list V) (x : V) :
+  length (removeV x xs) < length (x :: xs).
+  Proof. Admitted.
+
+(* Function version *)
+Set Printing Universes.
+
+Require Import Recdef.
+
+Function nubV {V:Type}{eqV:relation V}{equivV:@Equivalence V eqV}{eqDecV :
+@EqDec V eqV equivV} (l : list V) { measure length l} :=
+    match l with
+      | nil => nil
+      | x::xs => x :: @nubV V eqV equivV eqDecV (removeV x xs)
+    end.
+Proof. intros. apply remove_le. Qed.
+
+(* Program version *)
+
+Program Fixpoint nubV `{eqDecV : @EqDec V eqV equivV} (l : list V)
+        {  measure (@length V l) lt } :=
+    match l with
+      | nil => nil
+      | x::xs => x :: @nubV V eqV equivV eqDecV (removeV x xs) _
+    end.