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