Mercurial > 12ws.info2

comparison exercises/src/Exercise_9.hs @ 22:498aea38199b

Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
week 9 tutorial
author Markus Kaiser <markus.kaiser@in.tum.de>
date Wed, 19 Dec 2012 23:20:55 +0100
parents 3fea6fff7265
children
comparison
equal deleted inserted replaced
21:3fea6fff7265 22:498aea38199b
53 53
54 {---------------------------------------------------------------------} 54 {---------------------------------------------------------------------}
55 {- Aufgabe G9.1 -} 55 {- Aufgabe G9.1 -}
56 56
57 {- 57 {-
58 Lemma mirror (mirror t) = t 58 Lemma(t): mirror (mirror t) = t
59 Proof by structural induction on t 59 Proof by structural induction on t
60 60
61 Base case: 61 Base case: Lemma(Empty)
62 To show: 62 To show: mirror (mirror Empty) = Empty
63 mirror (mirror Empty)
64 = mirror Empty mirror_Empty
65 = Empty mirror_Empty
63 66
64 Induction step: 67 Induction step: Lemma(l), Lemma(r) => Lemma((Node x l r))
65 IH1: 68 IH1: mirror (mirror l) = l
66 IH2: 69 IH2: mirror (mirror r) = r
67 To show: 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
68 76
69 QED? 77 QED!
70 -} 78 -}
71 79
72 80
73 81
74 {---------------------------------------------------------------------} 82 {---------------------------------------------------------------------}
75 {- Aufgabe G9.2 -} 83 {- Aufgabe G9.2 -}
76 84
77 balanced :: Tree a -> Bool 85 balanced :: Tree a -> Bool
78 balanced t = undefined 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
79 90
80 91
81 92
82 {---------------------------------------------------------------------} 93 {---------------------------------------------------------------------}
83 {- Aufgabe G9.3 -} 94 {- Aufgabe G9.3 -}
84 95
85 type Coords = (Int, Int) 96 type Coords = (Int, Int)
86 data Shape = Missing 97 data Shape =
98 Line Coords Coords
99 | Circle Coords Int
100
87 101
88 move :: Coords -> Shape -> Shape 102 move :: Coords -> Shape -> Shape
89 move (x,y) _ = undefined 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
90 106
91 polygon :: [Shape] -> Bool 107 polygon :: [Shape] -> Bool
92 polygon _ = undefined 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
93 114
94 115
95 116
96 {---------------------------------------------------------------------} 117 {---------------------------------------------------------------------}
97 {- Aufgabe H9.1 -} 118 {- Aufgabe H9.1 -}