proposition: Lemma fold_add_subset' : forall (A : Set)(eqd : eq_dec A)(ls1 ls2 : list A)(f : A -> Rat) init1 init2, init1 == init2 -> NoDup ls1 -> NoDup ls2 -> (forall a, In a ls1 -> In a ls2) -> (forall a, In a ls2 -> (~In a ls1) -> (f a) == 0) -> fold_left (fun r a => r + (f a)) ls1 init1 == fold_left (fun r a => r + (f a)) ls2 init2.
proof: Proof. intuition. erewrite <- matchOrder_firstn at 1. eapply eqRat_symm. eapply eqRat_trans. eapply fold_add_rat_perm. eapply matchOrder_permutation. eapply H0. eauto. intuition. eapply eqRat_refl. intuition. eapply eqRat_refl. eapply eqRat_symm. eapply fold_add_matchOrder; intuition. eapply permutation_NoDup. eapply matchOrder_permutation; eauto. eauto. eapply H3. eapply matchOrder_In. eapply H0. trivial. intuition. eauto. intuition. eapply H5. rewrite matchOrder_firstn; trivial. trivial. trivial. trivial. Unshelve. trivial. Qed.
imports: FCF.Rat List Permutation Arith FCF.EqDec FCF.StdNat Bool Permutation