equal
deleted
inserted
replaced
122 lemma (in monoid_add) length_concat: |
122 lemma (in monoid_add) length_concat: |
123 "length (concat xss) = sum_list (map length xss)" |
123 "length (concat xss) = sum_list (map length xss)" |
124 by (induct xss) simp_all |
124 by (induct xss) simp_all |
125 |
125 |
126 lemma (in monoid_add) length_product_lists: |
126 lemma (in monoid_add) length_product_lists: |
127 "length (product_lists xss) = foldr op * (map length xss) 1" |
127 "length (product_lists xss) = foldr ( * ) (map length xss) 1" |
128 proof (induct xss) |
128 proof (induct xss) |
129 case (Cons xs xss) then show ?case by (induct xs) (auto simp: length_concat o_def) |
129 case (Cons xs xss) then show ?case by (induct xs) (auto simp: length_concat o_def) |
130 qed simp |
130 qed simp |
131 |
131 |
132 lemma (in monoid_add) sum_list_map_filter: |
132 lemma (in monoid_add) sum_list_map_filter: |
232 by (simp add: sum_list_distinct_conv_sum_set) |
232 by (simp add: sum_list_distinct_conv_sum_set) |
233 |
233 |
234 text \<open>General equivalence between @{const sum_list} and @{const sum}\<close> |
234 text \<open>General equivalence between @{const sum_list} and @{const sum}\<close> |
235 lemma (in monoid_add) sum_list_sum_nth: |
235 lemma (in monoid_add) sum_list_sum_nth: |
236 "sum_list xs = (\<Sum> i = 0 ..< length xs. xs ! i)" |
236 "sum_list xs = (\<Sum> i = 0 ..< length xs. xs ! i)" |
237 using interv_sum_list_conv_sum_set_nat [of "op ! xs" 0 "length xs"] by (simp add: map_nth) |
237 using interv_sum_list_conv_sum_set_nat [of "(!) xs" 0 "length xs"] by (simp add: map_nth) |
238 |
238 |
239 lemma sum_list_map_eq_sum_count: |
239 lemma sum_list_map_eq_sum_count: |
240 "sum_list (map f xs) = sum (\<lambda>x. count_list xs x * f x) (set xs)" |
240 "sum_list (map f xs) = sum (\<lambda>x. count_list xs x * f x) (set xs)" |
241 proof(induction xs) |
241 proof(induction xs) |
242 case (Cons x xs) |
242 case (Cons x xs) |
290 can be upper-bounded by summation over \<open>{0..<n}\<close>.\<close> |
290 can be upper-bounded by summation over \<open>{0..<n}\<close>.\<close> |
291 |
291 |
292 lemma sorted_wrt_less_sum_mono_lowerbound: |
292 lemma sorted_wrt_less_sum_mono_lowerbound: |
293 fixes f :: "nat \<Rightarrow> ('b::ordered_comm_monoid_add)" |
293 fixes f :: "nat \<Rightarrow> ('b::ordered_comm_monoid_add)" |
294 assumes mono: "\<And>x y. x\<le>y \<Longrightarrow> f x \<le> f y" |
294 assumes mono: "\<And>x y. x\<le>y \<Longrightarrow> f x \<le> f y" |
295 shows "sorted_wrt (op <) ns \<Longrightarrow> |
295 shows "sorted_wrt (<) ns \<Longrightarrow> |
296 (\<Sum>i\<in>{0..<length ns}. f i) \<le> (\<Sum>i\<leftarrow>ns. f i)" |
296 (\<Sum>i\<in>{0..<length ns}. f i) \<le> (\<Sum>i\<leftarrow>ns. f i)" |
297 proof (induction ns rule: rev_induct) |
297 proof (induction ns rule: rev_induct) |
298 case Nil |
298 case Nil |
299 then show ?case by simp |
299 then show ?case by simp |
300 next |
300 next |
353 by (simp add: interv_sum_list_conv_sum_set_nat) |
353 by (simp add: interv_sum_list_conv_sum_set_nat) |
354 |
354 |
355 lemma sum_list_transfer[transfer_rule]: |
355 lemma sum_list_transfer[transfer_rule]: |
356 includes lifting_syntax |
356 includes lifting_syntax |
357 assumes [transfer_rule]: "A 0 0" |
357 assumes [transfer_rule]: "A 0 0" |
358 assumes [transfer_rule]: "(A ===> A ===> A) op + op +" |
358 assumes [transfer_rule]: "(A ===> A ===> A) (+) (+)" |
359 shows "(list_all2 A ===> A) sum_list sum_list" |
359 shows "(list_all2 A ===> A) sum_list sum_list" |
360 unfolding sum_list.eq_foldr [abs_def] |
360 unfolding sum_list.eq_foldr [abs_def] |
361 by transfer_prover |
361 by transfer_prover |
362 |
362 |
363 |
363 |