|
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 {- |
|
22
|
58 Lemma(t): mirror (mirror t) = t |
|
21
|
59 Proof by structural induction on t |
|
|
60 |
|
22
|
61 Base case: Lemma(Empty) |
|
|
62 To show: mirror (mirror Empty) = Empty |
|
|
63 mirror (mirror Empty) |
|
|
64 = mirror Empty mirror_Empty |
|
|
65 = Empty mirror_Empty |
|
21
|
66 |
|
22
|
67 Induction step: Lemma(l), Lemma(r) => Lemma((Node x l r)) |
|
|
68 IH1: mirror (mirror l) = l |
|
|
69 IH2: mirror (mirror r) = r |
|
|
70 To show: mirror (mirror (Node x l r)) = Node x l r |
|
|
71 mirror (mirror (Node x l r)) |
|
|
72 = mirror (Node x (mirror r) (mirror l)) mirror_Node |
|
|
73 = Node x (mirror (mirror l)) (mirror (mirror r)) mirror_Node |
|
|
74 = Node x l (mirror (mirror r)) IH1 |
|
|
75 = Node x l r IH2 |
|
21
|
76 |
|
22
|
77 QED! |
|
21
|
78 -} |
|
|
79 |
|
|
80 |
|
|
81 |
|
|
82 {---------------------------------------------------------------------} |
|
|
83 {- Aufgabe G9.2 -} |
|
|
84 |
|
|
85 balanced :: Tree a -> Bool |
|
22
|
86 balanced t = dist max t - dist min t <= 1 |
|
|
87 where |
|
|
88 dist f (Node _ l r) = 1 + f (dist f l) (dist f r) |
|
|
89 dist _ Empty = 0 |
|
21
|
90 |
|
|
91 |
|
|
92 |
|
|
93 {---------------------------------------------------------------------} |
|
|
94 {- Aufgabe G9.3 -} |
|
|
95 |
|
|
96 type Coords = (Int, Int) |
|
22
|
97 data Shape = |
|
|
98 Line Coords Coords |
|
|
99 | Circle Coords Int |
|
|
100 |
|
21
|
101 |
|
|
102 move :: Coords -> Shape -> Shape |
|
22
|
103 move (x,y) (Line (a,b) (c,d)) = Line (a+x, b+y) (c+x, d+y) |
|
|
104 move (x,y) (Circle (a,b) r) = Circle (a+x, b+y) r |
|
|
105 |
|
21
|
106 |
|
|
107 polygon :: [Shape] -> Bool |
|
22
|
108 polygon ((Line from to) : ss) = polygon' from to ss |
|
|
109 where |
|
|
110 polygon' f t [] = f == t |
|
|
111 polygon' f t ((Line lf lt) : ss) = t == lf && polygon' f lt ss |
|
|
112 polygon' _ _ _ = False |
|
|
113 polygon _ = False |
|
21
|
114 |
|
|
115 |
|
|
116 |
|
|
117 {---------------------------------------------------------------------} |
|
|
118 {- Aufgabe H9.1 -} |
|
|
119 |
|
|
120 {- |
|
|
121 Proof me! |
|
|
122 -} |
|
|
123 |
|
|
124 |
|
|
125 |
|
|
126 {---------------------------------------------------------------------} |
|
|
127 {- Aufgabe H9.2 -} |
|
|
128 |
|
|
129 inorder :: Tree a -> [a] |
|
|
130 inorder = undefined |
|
|
131 |
|
|
132 preorder :: Tree a -> [a] |
|
|
133 preorder = undefined |
|
|
134 |
|
|
135 postorder :: Tree a -> [a] |
|
|
136 postorder = undefined |
|
|
137 |
|
|
138 |
|
|
139 |
|
|
140 {---------------------------------------------------------------------} |
|
|
141 {- Aufgabe H9.3 -} |
|
|
142 |
|
|
143 -- makeBalanced :: Int -> SkeleTree |
|
|
144 -- makeBalanced = undefined |
|
|
145 -- |
|
|
146 -- makeAllBalanced :: Int -> SkeleTree |
|
|
147 -- makeAllBalanced = undefined |
|
|
148 |
|
|
149 |
|
|
150 |
|
|
151 {---------------------------------------------------------------------} |
|
|
152 {- Aufgabe H9.4 -} |
|
|
153 |
|
|
154 find23 :: Ord a => a -> Tree23 a -> Bool |
|
|
155 find23 = undefined |
