proposition: Lemma Permutation_partition {A} (f : A -> bool) : forall (ls : list A), Permutation ls ((List.filter f ls) ++ (List.filter (fun x => negb (f x)) ls)).
proof: Proof. intros. induction ls. - constructor. - simpl. destruct (f a); simpl. + constructor. assumption. + rewrite <- Permutation_middle. constructor. assumption. Qed.
imports: Fiat.QueryStructure.Implementation.DataStructures.Bags.BagsInterface Fiat.QueryStructure.Implementation.DataStructures.Bags.BagsProperties Coq.Arith.PeanoNat Coq.FSets.FMapInterface Coq.FSets.FMapFacts Coq.FSets.FMapAVL Fiat.Common Fiat.Common.List.ListFacts Fiat.Common.List.FlattenList Fiat.Common.SetEqProperties Fiat.Common.FMapExtensions Fiat.Common.List.PermutationFacts