Introduce `set_bind` and associated lemmas.

theories/fin_sets.v

@@ -27,6 +27,11 @@ Definition set_map `{Elements A C, Singleton B D, Empty D, Union D}
 Typeclasses Opaque set_map.
 Global Instance: Params (@set_map) 8 := {}.
 
+Definition set_bind `{Elements A SA, Empty SB, Union SB}
+    (f : A → SB) (X : SA) : SB :=
+  ⋃ (f <$> elements X).
+Typeclasses Opaque set_bind.
+
 Global Instance set_fresh `{Elements A C, Fresh A (list A)} : Fresh A C :=
   fresh ∘ elements.
 Typeclasses Opaque set_fresh.
@@ -436,6 +441,53 @@ Section map.
   Proof. unfold_leibniz. apply set_map_singleton. Qed.
 End map.
 
+(** * Bind *)
+Section set_bind.
+  Context `{FinSet B SB}.
+
+  Local Notation set_bind := (set_bind (A:=A) (SA:=C) (SB:=SB)).
+
+  Lemma elem_of_set_bind (f : A → SB) (X : C) y :
+    y ∈ set_bind f X ↔ ∃ x, x ∈ X ∧ y ∈ f x.
+  Proof.
+    unfold set_bind. rewrite !elem_of_union_list. set_solver.
+  Qed.
+
+  Global Instance set_unfold_set_bind (f : A → SB) (X : C)
+         (y : B) (P : A → B → Prop) (Q : A → Prop) :
+    (∀ x y, SetUnfoldElemOf y (f x) (P x y)) →
+    (∀ x, SetUnfoldElemOf x X (Q x)) →
+    SetUnfoldElemOf y (set_bind f X) (∃ x, Q x ∧ P x y).
+  Proof.
+    intros HSU1 HSU2. constructor.
+    rewrite elem_of_set_bind. set_solver.
+  Qed.
+
+  Lemma set_bind_ext (f g : A → SB) (X Y : C) :
+    (∀ x, x ∈ X → x ∈ Y → f x ≡ g x) → X ≡ Y → set_bind f X ≡ set_bind g Y.
+  Proof.
+    intros Hfg HXY b. rewrite !elem_of_set_bind. set_solver.
+  Qed.
+
+  Global Instance set_bind_proper : Proper (pointwise_relation _ (≡) ==> (≡) ==> (≡)) set_bind.
+  Proof. intros f1 f2 Hf X1 X2 HX. by apply set_bind_ext. Qed.
+
+  Global Instance set_bind_subset f : Proper ((⊆) ==> (⊆)) (set_bind f).
+  Proof. intros X Y HXY. set_solver. Qed.
+
+  Lemma set_bind_singleton f x : set_bind f {[x]} ≡ f x.
+  Proof. set_solver. Qed.
+  Lemma set_bind_singleton_L `{!LeibnizEquiv SB} f x : set_bind f {[x]} = f x.
+  Proof. unfold_leibniz. apply set_bind_singleton. Qed.
+
+  Lemma set_bind_disj_union f (X Y : C) :
+    X ## Y → set_bind f (X ∪ Y) ≡ set_bind f X ∪ set_bind f Y.
+  Proof. set_solver. Qed.
+  Lemma set_bind_disj_union_L `{!LeibnizEquiv SB} f (X Y : C) :
+    X ## Y → set_bind f (X ∪ Y) = set_bind f X ∪ set_bind f Y.
+  Proof. unfold_leibniz. apply set_bind_disj_union. Qed.
+End set_bind.
+
 (** * Decision procedures *)
 Lemma set_Forall_elements P X : set_Forall P X ↔ Forall P (elements X).
 Proof. rewrite Forall_forall. by setoid_rewrite elem_of_elements. Qed.

[Paolo G. Giarrusso]

This should come with a Params instance.

[Paolo G. Giarrusso]

Looks like it should be

-Typeclasses Opaque set_bind.
+Typeclasses Opaque set_bind.
+Global Instance: Params (@set_bind) 6 := {}.

the number should be "total argument count - 2", since the Proper instance only enables setoid rewriting in the last 2 arguments.

[Robbert Krebbers]

Doesn't set_solver immediately finish this goal?

[Dan Frumin]

It does solve the goal, but it takes quite some time. The proof script above is instantenous .

[Robbert Krebbers]

The problem is that set_solver performs setoid_subst and since the Proper for set_bind is not there it takes a while for setoid_subst to fail. And then swapping the two lemmas is not easy either, since the Proper makes use of this lemma.

I tried to see if solve_proper can prove the Proper, but that fails.

Can you maybe add this as a comment?

[Paolo G. Giarrusso]

That makes sense, but there's a missing Params instance that we should add. If we're lucky, setoid_subst will become fast.

!383 (diffs, comment 82508)

[Paolo G. Giarrusso]

Indeed, before Params, EDIT: Time set_solver tells me:

Finished transaction in 1.526 secs (1.508u,0.014s) (successful)

After Params, EDIT: Time set_solver tells me:

Finished transaction in 0.343 secs (0.342u,0.001s) (successful)

[Paolo G. Giarrusso]

Time rewrite !elem_of_set_bind; set_solver. still takes <= 0.05s. But dfrumin/coq-stdpp!1 (closed) has an alternative proposal with a few more revisions.

[Paolo G. Giarrusso]

I just noticed we have two Proper instances with different arities here... Do stdpp/iris ever do that? dfrumin/coq-stdpp!1 (closed) addresses that too.