Mercurial > 12ws.info2
annotate exercises/src/Exercise_14.hs @ 37:15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Wed, 06 Feb 2013 21:48:45 +0100 |
| parents | 89feab98266f |
| children |
| rev | line source |
|---|---|
| 35 | 1 module Exercise_14 where |
| 2 import qualified Data.List | |
| 36 | 3 import Test.QuickCheck |
| 35 | 4 |
| 5 | |
| 6 {---------------------------------------------------------------------} | |
| 7 {- Aufgabe G14.1 -} | |
| 8 | |
| 9 delete :: Eq a => a -> [a] -> [a] | |
| 10 delete = Data.List.delete {- falsche Implementierung -} | |
| 11 | |
| 12 | |
| 36 | 13 -- Reimplementierung: Vollständig? |
| 14 prop_reimplement x xs = | |
| 15 delete x xs == filter (/=x) xs | |
| 35 | 16 |
| 36 | 17 -- Induktive Tests: Vollständig |
| 18 prop_nil :: Int -> Bool | |
| 19 prop_nil x = null (delete x []) | |
| 20 | |
| 21 prop_cons :: Char -> Char -> [Char] -> Bool | |
| 22 prop_cons x y xs = | |
| 23 delete x (y : xs) == | |
| 24 if x == y then delete x xs | |
| 25 else y : delete x xs | |
| 26 | |
| 27 -- Kombinatorische Tests: Vollständig | |
| 28 prop_single x y = | |
| 29 delete x [y] == | |
| 30 if x == y then [] | |
| 31 else [y] | |
| 35 | 32 |
| 36 | 33 prop_append x xs ys = |
| 34 delete x (xs ++ ys) == delete x xs ++ delete x ys | |
| 35 | |
| 36 -- Spezifische Tests: Unvollständig | |
| 37 prop_noelem x xs = x `notElem` delete x xs | |
| 38 | |
| 39 prop_neutrality x xs = x `notElem` xs ==> xs == delete x xs | |
| 40 | |
| 41 prop_nothingNew x xs = delete x xs `subseq` xs | |
| 42 where | |
| 43 subseq = undefined | |
| 44 | |
| 45 prop_length x xs = | |
| 46 length xs - length [c | c <- xs, c == x] == length (delete x xs) | |
| 47 | |
| 48 prop_idem x xs = d == delete x d | |
| 49 where d = delete x xs | |
| 50 | |
| 51 -- Beispiele: Sehr fragwürdig | |
| 52 prop_example x = delete x (replicate 10 x) == [] | |
| 35 | 53 |
| 54 | |
| 55 | |
| 56 {---------------------------------------------------------------------} | |
| 36 | 57 {- Aufgabe G14.2 -} |
| 58 | |
|
37
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
59 -- Beispiele zur Endrekursion |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
60 sum1 :: Int -> Int |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
61 sum1 0 = 0 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
62 sum1 n = n + sum1 (n - 1) |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
63 {- |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
64 sum1 3 = 3 + sum1 2 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
65 sum1 2 = 2 + sum1 1 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
66 sum1 1 = 1 + sum1 0 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
67 sum1 0 = 0 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
68 sum1 1 = 1 + 0 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
69 = 1 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
70 sum1 2 = 2 + 1 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
71 = 3 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
72 sum1 3 = 3 + 3 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
73 = 6 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
74 -} |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
75 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
76 sum2 :: Int -> Int |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
77 sum2 = sum2_end 0 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
78 where |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
79 sum2_end acc 0 = acc |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
80 sum2_end acc n = sum2_end (acc + n) (n - 1) |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
81 {- |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
82 sum2 3 = sum2_end 0 3 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
83 = sum2_end 3 2 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
84 = sum2_end 5 1 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
85 = sum2_end 6 0 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
86 = 6 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
87 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
88 -} |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
89 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
90 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
91 -- Concats |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
92 -- Nicht Endrekursiv |
| 36 | 93 concat' :: [[a]] -> [a] |
| 94 concat' [] = [] | |
| 95 concat' (xs:xss) = xs ++ concat' xss | |
| 96 | |
|
37
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
97 -- O(n) |
| 36 | 98 concat'' :: [[a]] -> [a] |
|
37
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
99 concat'' yss = go [] (reverse yss) |
| 36 | 100 where |
| 101 go acc [] = acc | |
| 102 go acc (xs:xss) = go (xs ++ acc) xss | |
| 103 | |
|
37
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
104 -- O(n^2) |
| 36 | 105 concat''' :: [[a]] -> [a] |
|
37
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
106 concat''' = go [] |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
107 where |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
108 go acc [] = acc |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
109 go acc (xs:xss) = go (acc ++ xs) xss |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
110 |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
111 -- Mit Fold |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
112 concat'''' :: [[a]] -> [a] |
|
15e527f4b92e
add some more examples to G14.2 (thanks Tobi)
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
36
diff
changeset
|
113 concat'''' = foldr (++) [] |
| 36 | 114 |
| 115 | |
| 116 | |
| 117 {---------------------------------------------------------------------} | |
| 118 {- Aufgabe G14.3 -} | |
| 35 | 119 |
| 120 {- | |
| 121 | |
| 122 map (*2) (1 : threes) !! 1 | |
| 36 | 123 = ((*2) 1 : map (*2) threes) !! 1 |
| 124 = map (*2) threes !! 0 | |
| 125 = map (*2) (3: threes) !! 0 | |
| 126 = ((*2) 3 : map (*2) threes) !! 0 | |
| 127 = (*2) 3 | |
| 128 = 3 * 2 | |
| 129 = 6 | |
| 35 | 130 |
| 36 | 131 |
| 132 ((\f -> \x -> x + f 2) (\y -> y * 2)) (3 + 1) | |
| 133 = (\x -> x + (\y -> y * 2) 2) (3 + 1) | |
| 134 = (3 + 1) + (\y -> y * 2) 2 | |
| 135 = 4 + (\y -> y * 2) 2 | |
| 136 = 4 + 2 * 2 | |
| 137 = 4 + 4 | |
| 138 = 8 | |
| 139 | |
| 35 | 140 |
| 141 filter (/=3) threes | |
| 36 | 142 = filter (/=3) (3 : threes) |
| 143 = filter (/=3) threes | |
| 144 --> terminiert nicht | |
| 145 | |
| 146 threes = 3 : threes | |
| 35 | 147 |
| 148 -} | |
| 149 | |
| 150 | |
| 151 | |
| 152 {---------------------------------------------------------------------} | |
| 153 {- Aufgabe H14.1 -} | |
| 154 | |
| 155 {- Type me! -} | |
| 156 | |
| 157 | |
| 158 | |
| 159 {---------------------------------------------------------------------} | |
| 160 {- Aufgabe H14.2 -} | |
| 161 | |
| 162 {- Proof me! -} | |
| 163 | |
| 164 | |
| 165 | |
| 166 {---------------------------------------------------------------------} | |
| 167 {- Aufgabe H14.3 -} | |
| 168 | |
| 169 filterMap :: (a -> Maybe b) -> [a] -> [b] | |
| 170 filterMap = undefined |