doc-src/TutorialI/ToyList2/ToyList.thy

-theory ToyList
-imports Datatype
-begin
-
-datatype 'a list = Nil                          ("[]")
-                 | Cons 'a "'a list"            (infixr "#" 65)
-
-(* This is the append function: *)
-primrec app :: "'a list => 'a list => 'a list"  (infixr "@" 65)
-where
-"[] @ ys       = ys" |
-"(x # xs) @ ys = x # (xs @ ys)"
-
-primrec rev :: "'a list => 'a list" where
-"rev []        = []" |
-"rev (x # xs)  = (rev xs) @ (x # [])"
-lemma app_Nil2 [simp]: "xs @ [] = xs"
-apply(induct_tac xs)
-apply(auto)
-done
-
-lemma app_assoc [simp]: "(xs @ ys) @ zs = xs @ (ys @ zs)"
-apply(induct_tac xs)
-apply(auto)
-done
-
-lemma rev_app [simp]: "rev(xs @ ys) = (rev ys) @ (rev xs)"
-apply(induct_tac xs)
-apply(auto)
-done
-
-theorem rev_rev [simp]: "rev(rev xs) = xs"
-apply(induct_tac xs)
-apply(auto)
-done
-
-end