proposition: Lemma fold_left_mono_filter: forall {A} (f: Z -> A -> Z) (l: list A) (h: A -> bool) s, (forall a b, a <= f a b) -> (forall a b1 b2, f (f a b1) b2 = f (f a b2) b1) -> fold_left f (filter h l) s <= fold_left f l s.
proof: Proof. intros. remember (fun x: A => negb (h x)) as g. assert (Permutation (filter h l ++ filter g l) l) by (symmetry; apply filter_perm; intros; subst; apply Bool.negb_involutive_reverse). apply (fold_left_Z_mono f _ _ _ s H H0 H1). Qed.
imports: Coq.Lists.List Coq.micromega.Lia Coq.Sorting.Permutation Coq.ZArith.ZArith_base Coq.ZArith.Zcomplements Coq.Logic.FunctionalExtensionality CertiGraph.lib.Coqlib CertiGraph.lib.EquivDec_ext VST.zlist.sublist VST.zlist.list_solver