doc-src/TutorialI/ToyList2/ToyList.thy

--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/doc-src/TutorialI/ToyList2/ToyList.thy	Mon Jul 30 17:37:34 2012 +0200
@@ -0,0 +1,37 @@
+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