Mercurial > 12ws.info2

comparison exercises/src/Exercise_9.hs @ 21:3fea6fff7265

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
week 9
author Markus Kaiser <markus.kaiser@in.tum.de>
date Wed, 12 Dec 2012 20:32:09 +0100
parents
children 498aea38199b
comparison
equal deleted inserted replaced
20:6d43207984ec 21:3fea6fff7265
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