# HG changeset patch
# User Markus Kaiser <markus.kaiser@in.tum.de>
# Date 1355340729 -3600
# Node ID 3fea6fff726577d8c09821e3cc0b5f6367564cff
# Parent  6d43207984ec5774e3107ac9c0c54508a545ee7e
week 9

diff -r 6d43207984ec -r 3fea6fff7265 blatt9.pdf
Binary file blatt9.pdf has changed
diff -r 6d43207984ec -r 3fea6fff7265 exercises/src/Exercise_9.hs
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/exercises/src/Exercise_9.hs	Wed Dec 12 20:32:09 2012 +0100
@@ -0,0 +1,134 @@
+module Exercise_9 where
+import Test.QuickCheck
+import Control.Monad
+
+{- Library DO NOT CHANGE -}
+data Tree a = Empty | Node a (Tree a) (Tree a)
+  deriving (Eq, Show)
+
+data Tree23 a = Leaf a
+              | Branch2 (Tree23 a) a (Tree23 a)
+              | Branch3 (Tree23 a) a (Tree23 a) a (Tree23 a)
+  deriving Show
+
+mirror :: Tree a -> Tree a
+mirror Empty = Empty
+mirror (Node x l r) = Node x (mirror r) (mirror l)
+
+flat :: Tree a -> [a]
+flat Empty = []
+flat (Node x l r) = flat l ++ [x] ++ flat r
+
+-- allow QuickCheck to generate arbitrary values of type Tree
+instance Arbitrary a => Arbitrary (Tree a) where
+  arbitrary = sized tree
+    where
+    tree 0 = return Empty
+    tree n | n > 0 = oneof [return Empty,
+      liftM3 Node arbitrary (tree (n `div` 2)) (tree (n `div` 2))]
+  shrink Empty = []
+  shrink (Node x l r) = l : r : map (\l' -> Node x l' r) (shrink l)
+        ++ map (\r' -> Node x l r') (shrink r)
+
+-- examples for G9.2
+balancedTrees =
+    [ Empty
+    , Node 0 Empty Empty
+    , Node 0 (Node 1 Empty Empty) Empty
+    , Node 4 (Node 2 Empty (Node 5 Empty Empty)) (Node 0 Empty Empty)
+    , Node 1 (Node 0 Empty (Node 3 Empty Empty))
+             (Node 0 Empty (Node 3 Empty Empty))
+    ]
+
+unbalancedTrees =
+    [ Node 3 (Node 2 Empty (Node 1 Empty Empty)) Empty
+    , Node 4 (Node 3 (Node 2 (Node 1 Empty Empty) Empty) Empty)
+             (Node 3 Empty (Node 2 Empty (Node 1 Empty Empty)))
+    , Node 9 (Node 8 (Node 7 Empty Empty ) Empty)
+             (Node 1 (Node 0 Empty (Node 3 Empty Empty))
+                     (Node 0 Empty (Node 3 Empty Empty)))
+    ]
+{- End Library -}
+
+
+{---------------------------------------------------------------------}
+{- Aufgabe G9.1 -}
+
+{-
+Lemma mirror (mirror t) = t
+Proof by structural induction on t
+
+Base case:
+To show:
+
+Induction step:
+IH1:
+IH2:
+To show:
+
+QED?
+-}
+
+
+
+{---------------------------------------------------------------------}
+{- Aufgabe G9.2 -}
+
+balanced :: Tree a -> Bool
+balanced t = undefined
+
+
+
+{---------------------------------------------------------------------}
+{- Aufgabe G9.3 -}
+
+type Coords = (Int, Int)
+data Shape = Missing
+
+move :: Coords -> Shape -> Shape
+move (x,y) _ = undefined
+
+polygon :: [Shape] -> Bool
+polygon _ = undefined
+
+
+
+{---------------------------------------------------------------------}
+{- Aufgabe H9.1 -}
+
+{- 
+Proof me!
+-}
+
+
+
+{---------------------------------------------------------------------}
+{- Aufgabe H9.2 -}
+
+inorder :: Tree a -> [a]
+inorder = undefined
+
+preorder :: Tree a -> [a]
+preorder = undefined
+
+postorder :: Tree a -> [a]
+postorder = undefined
+
+
+
+{---------------------------------------------------------------------}
+{- Aufgabe H9.3 -}
+
+-- makeBalanced :: Int -> SkeleTree
+-- makeBalanced = undefined
+--
+-- makeAllBalanced :: Int -> SkeleTree
+-- makeAllBalanced = undefined
+
+
+
+{---------------------------------------------------------------------}
+{- Aufgabe H9.4 -}
+
+find23 :: Ord a => a -> Tree23 a -> Bool
+find23 = undefined