|
21
|
1 module Exercise_9 where |
|
|
2 import Test.QuickCheck |
|
|
3 import Control.Monad |
|
|
4 |
|
|
5 {- Library DO NOT CHANGE -} |
|
|
6 data Tree a = Empty | Node a (Tree a) (Tree a) |
|
|
7 deriving (Eq, Show) |
|
|
8 |
|
|
9 data Tree23 a = Leaf a |
|
|
10 | Branch2 (Tree23 a) a (Tree23 a) |
|
|
11 | Branch3 (Tree23 a) a (Tree23 a) a (Tree23 a) |
|
|
12 deriving Show |
|
|
13 |
|
|
14 mirror :: Tree a -> Tree a |
|
|
15 mirror Empty = Empty |
|
|
16 mirror (Node x l r) = Node x (mirror r) (mirror l) |
|
|
17 |
|
|
18 flat :: Tree a -> [a] |
|
|
19 flat Empty = [] |
|
|
20 flat (Node x l r) = flat l ++ [x] ++ flat r |
|
|
21 |
|
|
22 -- allow QuickCheck to generate arbitrary values of type Tree |
|
|
23 instance Arbitrary a => Arbitrary (Tree a) where |
|
|
24 arbitrary = sized tree |
|
|
25 where |
|
|
26 tree 0 = return Empty |
|
|
27 tree n | n > 0 = oneof [return Empty, |
|
|
28 liftM3 Node arbitrary (tree (n `div` 2)) (tree (n `div` 2))] |
|
|
29 shrink Empty = [] |
|
|
30 shrink (Node x l r) = l : r : map (\l' -> Node x l' r) (shrink l) |
|
|
31 ++ map (\r' -> Node x l r') (shrink r) |
|
|
32 |
|
|
33 -- examples for G9.2 |
|
|
34 balancedTrees = |
|
|
35 [ Empty |
|
|
36 , Node 0 Empty Empty |
|
|
37 , Node 0 (Node 1 Empty Empty) Empty |
|
|
38 , Node 4 (Node 2 Empty (Node 5 Empty Empty)) (Node 0 Empty Empty) |
|
|
39 , Node 1 (Node 0 Empty (Node 3 Empty Empty)) |
|
|
40 (Node 0 Empty (Node 3 Empty Empty)) |
|
|
41 ] |
|
|
42 |
|
|
43 unbalancedTrees = |
|
|
44 [ Node 3 (Node 2 Empty (Node 1 Empty Empty)) Empty |
|
|
45 , Node 4 (Node 3 (Node 2 (Node 1 Empty Empty) Empty) Empty) |
|
|
46 (Node 3 Empty (Node 2 Empty (Node 1 Empty Empty))) |
|
|
47 , Node 9 (Node 8 (Node 7 Empty Empty ) Empty) |
|
|
48 (Node 1 (Node 0 Empty (Node 3 Empty Empty)) |
|
|
49 (Node 0 Empty (Node 3 Empty Empty))) |
|
|
50 ] |
|
|
51 {- End Library -} |
|
|
52 |
|
|
53 |
|
|
54 {---------------------------------------------------------------------} |
|
|
55 {- Aufgabe G9.1 -} |
|
|
56 |
|
|
57 {- |
|
|
58 Lemma mirror (mirror t) = t |
|
|
59 Proof by structural induction on t |
|
|
60 |
|
|
61 Base case: |
|
|
62 To show: |
|
|
63 |
|
|
64 Induction step: |
|
|
65 IH1: |
|
|
66 IH2: |
|
|
67 To show: |
|
|
68 |
|
|
69 QED? |
|
|
70 -} |
|
|
71 |
|
|
72 |
|
|
73 |
|
|
74 {---------------------------------------------------------------------} |
|
|
75 {- Aufgabe G9.2 -} |
|
|
76 |
|
|
77 balanced :: Tree a -> Bool |
|
|
78 balanced t = undefined |
|
|
79 |
|
|
80 |
|
|
81 |
|
|
82 {---------------------------------------------------------------------} |
|
|
83 {- Aufgabe G9.3 -} |
|
|
84 |
|
|
85 type Coords = (Int, Int) |
|
|
86 data Shape = Missing |
|
|
87 |
|
|
88 move :: Coords -> Shape -> Shape |
|
|
89 move (x,y) _ = undefined |
|
|
90 |
|
|
91 polygon :: [Shape] -> Bool |
|
|
92 polygon _ = undefined |
|
|
93 |
|
|
94 |
|
|
95 |
|
|
96 {---------------------------------------------------------------------} |
|
|
97 {- Aufgabe H9.1 -} |
|
|
98 |
|
|
99 {- |
|
|
100 Proof me! |
|
|
101 -} |
|
|
102 |
|
|
103 |
|
|
104 |
|
|
105 {---------------------------------------------------------------------} |
|
|
106 {- Aufgabe H9.2 -} |
|
|
107 |
|
|
108 inorder :: Tree a -> [a] |
|
|
109 inorder = undefined |
|
|
110 |
|
|
111 preorder :: Tree a -> [a] |
|
|
112 preorder = undefined |
|
|
113 |
|
|
114 postorder :: Tree a -> [a] |
|
|
115 postorder = undefined |
|
|
116 |
|
|
117 |
|
|
118 |
|
|
119 {---------------------------------------------------------------------} |
|
|
120 {- Aufgabe H9.3 -} |
|
|
121 |
|
|
122 -- makeBalanced :: Int -> SkeleTree |
|
|
123 -- makeBalanced = undefined |
|
|
124 -- |
|
|
125 -- makeAllBalanced :: Int -> SkeleTree |
|
|
126 -- makeAllBalanced = undefined |
|
|
127 |
|
|
128 |
|
|
129 |
|
|
130 {---------------------------------------------------------------------} |
|
|
131 {- Aufgabe H9.4 -} |
|
|
132 |
|
|
133 find23 :: Ord a => a -> Tree23 a -> Bool |
|
|
134 find23 = undefined |
