src/HOL/List.thy
changeset 20503 503ac4c5ef91
parent 20453 855f07fabd76
child 20588 c847c56edf0c
equal deleted inserted replaced
20502:08d227db6c74 20503:503ac4c5ef91
   309 apply blast
   309 apply blast
   310 done
   310 done
   311 
   311 
   312 lemma impossible_Cons [rule_format]: 
   312 lemma impossible_Cons [rule_format]: 
   313   "length xs <= length ys --> xs = x # ys = False"
   313   "length xs <= length ys --> xs = x # ys = False"
   314 apply (induct xs, auto)
   314 apply (induct xs)
       
   315 apply auto
   315 done
   316 done
   316 
   317 
   317 lemma list_induct2[consumes 1]: "\<And>ys.
   318 lemma list_induct2[consumes 1]: "\<And>ys.
   318  \<lbrakk> length xs = length ys;
   319  \<lbrakk> length xs = length ys;
   319    P [] [];
   320    P [] [];
  1354 done
  1355 done
  1355 
  1356 
  1356 lemma takeWhile_cong [fundef_cong, recdef_cong]:
  1357 lemma takeWhile_cong [fundef_cong, recdef_cong]:
  1357   "[| l = k; !!x. x : set l ==> P x = Q x |] 
  1358   "[| l = k; !!x. x : set l ==> P x = Q x |] 
  1358   ==> takeWhile P l = takeWhile Q k"
  1359   ==> takeWhile P l = takeWhile Q k"
  1359   by (induct k fixing: l, simp_all)
  1360   by (induct k arbitrary: l) (simp_all)
  1360 
  1361 
  1361 lemma dropWhile_cong [fundef_cong, recdef_cong]:
  1362 lemma dropWhile_cong [fundef_cong, recdef_cong]:
  1362   "[| l = k; !!x. x : set l ==> P x = Q x |] 
  1363   "[| l = k; !!x. x : set l ==> P x = Q x |] 
  1363   ==> dropWhile P l = dropWhile Q k"
  1364   ==> dropWhile P l = dropWhile Q k"
  1364   by (induct k fixing: l, simp_all)
  1365   by (induct k arbitrary: l, simp_all)
  1365 
  1366 
  1366 
  1367 
  1367 subsubsection {* @{text zip} *}
  1368 subsubsection {* @{text zip} *}
  1368 
  1369 
  1369 lemma zip_Nil [simp]: "zip [] ys = []"
  1370 lemma zip_Nil [simp]: "zip [] ys = []"
  1598 by (induct xs) auto
  1599 by (induct xs) auto
  1599 
  1600 
  1600 lemma foldl_cong [fundef_cong, recdef_cong]:
  1601 lemma foldl_cong [fundef_cong, recdef_cong]:
  1601   "[| a = b; l = k; !!a x. x : set l ==> f a x = g a x |] 
  1602   "[| a = b; l = k; !!a x. x : set l ==> f a x = g a x |] 
  1602   ==> foldl f a l = foldl g b k"
  1603   ==> foldl f a l = foldl g b k"
  1603   by (induct k fixing: a b l, simp_all)
  1604   by (induct k arbitrary: a b l) simp_all
  1604 
  1605 
  1605 lemma foldr_cong [fundef_cong, recdef_cong]:
  1606 lemma foldr_cong [fundef_cong, recdef_cong]:
  1606   "[| a = b; l = k; !!a x. x : set l ==> f x a = g x a |] 
  1607   "[| a = b; l = k; !!a x. x : set l ==> f x a = g x a |] 
  1607   ==> foldr f l a = foldr g k b"
  1608   ==> foldr f l a = foldr g k b"
  1608   by (induct k fixing: a b l, simp_all)
  1609   by (induct k arbitrary: a b l) simp_all
  1609 
  1610 
  1610 lemma foldr_foldl: "foldr f xs a = foldl (%x y. f y x) a (rev xs)"
  1611 lemma foldr_foldl: "foldr f xs a = foldl (%x y. f y x) a (rev xs)"
  1611 by (induct xs) auto
  1612 by (induct xs) auto
  1612 
  1613 
  1613 lemma foldl_foldr: "foldl f a xs = foldr (%x y. f y x) (rev xs) a"
  1614 lemma foldl_foldr: "foldl f a xs = foldr (%x y. f y x) (rev xs) a"