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