775 unfolding Finite_Set.fold_def |
775 unfolding Finite_Set.fold_def |
776 by (subst fold_graph_closed_eq[where B=B and g=g]) (auto simp: that) |
776 by (subst fold_graph_closed_eq[where B=B and g=g]) (auto simp: that) |
777 |
777 |
778 text \<open> |
778 text \<open> |
779 A tempting alternative for the definiens is |
779 A tempting alternative for the definiens is |
780 @{term "if finite A then THE y. fold_graph f z A y else e"}. |
780 \<^term>\<open>if finite A then THE y. fold_graph f z A y else e\<close>. |
781 It allows the removal of finiteness assumptions from the theorems |
781 It allows the removal of finiteness assumptions from the theorems |
782 \<open>fold_comm\<close>, \<open>fold_reindex\<close> and \<open>fold_distrib\<close>. |
782 \<open>fold_comm\<close>, \<open>fold_reindex\<close> and \<open>fold_distrib\<close>. |
783 The proofs become ugly. It is not worth the effort. (???) |
783 The proofs become ugly. It is not worth the effort. (???) |
784 \<close> |
784 \<close> |
785 |
785 |
786 lemma finite_imp_fold_graph: "finite A \<Longrightarrow> \<exists>x. fold_graph f z A x" |
786 lemma finite_imp_fold_graph: "finite A \<Longrightarrow> \<exists>x. fold_graph f z A x" |
787 by (induct rule: finite_induct) auto |
787 by (induct rule: finite_induct) auto |
788 |
788 |
789 |
789 |
790 subsubsection \<open>From @{const fold_graph} to @{term fold}\<close> |
790 subsubsection \<open>From \<^const>\<open>fold_graph\<close> to \<^term>\<open>fold\<close>\<close> |
791 |
791 |
792 context comp_fun_commute |
792 context comp_fun_commute |
793 begin |
793 begin |
794 |
794 |
795 lemma fold_graph_finite: |
795 lemma fold_graph_finite: |
866 by (auto simp: fold_def) |
866 by (auto simp: fold_def) |
867 |
867 |
868 lemma (in -) fold_empty [simp]: "fold f z {} = z" |
868 lemma (in -) fold_empty [simp]: "fold f z {} = z" |
869 by (auto simp: fold_def) |
869 by (auto simp: fold_def) |
870 |
870 |
871 text \<open>The various recursion equations for @{const fold}:\<close> |
871 text \<open>The various recursion equations for \<^const>\<open>fold\<close>:\<close> |
872 |
872 |
873 lemma fold_insert [simp]: |
873 lemma fold_insert [simp]: |
874 assumes "finite A" and "x \<notin> A" |
874 assumes "finite A" and "x \<notin> A" |
875 shows "fold f z (insert x A) = f x (fold f z A)" |
875 shows "fold f z (insert x A) = f x (fold f z A)" |
876 proof (rule fold_equality) |
876 proof (rule fold_equality) |
931 shows "Finite_Set.fold f z (A \<union> B) = Finite_Set.fold f (Finite_Set.fold f z A) B" |
931 shows "Finite_Set.fold f z (A \<union> B) = Finite_Set.fold f (Finite_Set.fold f z A) B" |
932 using assms(2,1,3) by induct simp_all |
932 using assms(2,1,3) by induct simp_all |
933 |
933 |
934 end |
934 end |
935 |
935 |
936 text \<open>Other properties of @{const fold}:\<close> |
936 text \<open>Other properties of \<^const>\<open>fold\<close>:\<close> |
937 |
937 |
938 lemma fold_image: |
938 lemma fold_image: |
939 assumes "inj_on g A" |
939 assumes "inj_on g A" |
940 shows "fold f z (g ` A) = fold (f \<circ> g) z A" |
940 shows "fold f z (g ` A) = fold (f \<circ> g) z A" |
941 proof (cases "finite A") |
941 proof (cases "finite A") |
1354 |
1354 |
1355 subsection \<open>Finite cardinality\<close> |
1355 subsection \<open>Finite cardinality\<close> |
1356 |
1356 |
1357 text \<open> |
1357 text \<open> |
1358 The traditional definition |
1358 The traditional definition |
1359 @{prop "card A \<equiv> LEAST n. \<exists>f. A = {f i |i. i < n}"} |
1359 \<^prop>\<open>card A \<equiv> LEAST n. \<exists>f. A = {f i |i. i < n}\<close> |
1360 is ugly to work with. |
1360 is ugly to work with. |
1361 But now that we have @{const fold} things are easy: |
1361 But now that we have \<^const>\<open>fold\<close> things are easy: |
1362 \<close> |
1362 \<close> |
1363 |
1363 |
1364 global_interpretation card: folding "\<lambda>_. Suc" 0 |
1364 global_interpretation card: folding "\<lambda>_. Suc" 0 |
1365 defines card = "folding.F (\<lambda>_. Suc) 0" |
1365 defines card = "folding.F (\<lambda>_. Suc) 0" |
1366 by standard rule |
1366 by standard rule |