equal
deleted
inserted
replaced
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 |