src/HOL/Groups_List.thy
changeset 67399 eab6ce8368fa
parent 66434 5d7e770c7d5d
child 67489 f1ba59ddd9a6
equal deleted inserted replaced
67398:5eb932e604a2 67399:eab6ce8368fa
   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