src/HOL/Finite_Set.thy
changeset 27611 2c01c0bdb385
parent 27430 1e25ac05cd87
child 27981 feb0c01cf0fb
equal deleted inserted replaced
27610:8882d47e075f 27611:2c01c0bdb385
   751   A Tutorial on the Universality and Expressiveness of Fold,
   751   A Tutorial on the Universality and Expressiveness of Fold,
   752   JFP 9:4 (355-372), 1999.
   752   JFP 9:4 (355-372), 1999.
   753 *}
   753 *}
   754 
   754 
   755 lemma fold_fusion:
   755 lemma fold_fusion:
   756   includes ab_semigroup_mult g
   756   assumes "ab_semigroup_mult g"
   757   assumes fin: "finite A"
   757   assumes fin: "finite A"
   758     and hyp: "\<And>x y. h (g x y) = times x (h y)"
   758     and hyp: "\<And>x y. h (g x y) = times x (h y)"
   759   shows "h (fold g j w A) = fold times j (h w) A"
   759   shows "h (fold g j w A) = fold times j (h w) A"
   760   using fin hyp by (induct set: finite) simp_all
   760 proof -
       
   761   interpret ab_semigroup_mult [g] by fact
       
   762   show ?thesis using fin hyp by (induct set: finite) simp_all
       
   763 qed
   761 
   764 
   762 lemma fold_cong:
   765 lemma fold_cong:
   763   "finite A \<Longrightarrow> (!!x. x:A ==> g x = h x) ==> fold times g z A = fold times h z A"
   766   "finite A \<Longrightarrow> (!!x. x:A ==> g x = h x) ==> fold times g z A = fold times h z A"
   764   apply (subgoal_tac "ALL C. C <= A --> (ALL x:C. g x = h x) --> fold times g z C = fold times h z C")
   767   apply (subgoal_tac "ALL C. C <= A --> (ALL x:C. g x = h x) --> fold times g z C = fold times h z C")
   765    apply simp
   768    apply simp