Mercurial > 12ws.info2
annotate exercises/src/Exercise_5.hs @ 13:8cc37c82619c
week 5 tutorial
| author | Markus Kaiser <markus.kaiser@in.tum.de> |
|---|---|
| date | Wed, 21 Nov 2012 19:28:26 +0100 |
| parents | 8496af3b866b |
| children |
| rev | line source |
|---|---|
| 11 | 1 module Exercise_5 where |
| 2 import Data.Maybe | |
| 13 | 3 import Data.List |
| 4 import Test.QuickCheck | |
| 11 | 5 |
| 6 {- Library DO NOT CHANGE -} | |
| 7 type State = Integer | |
| 8 type DA = (State, State -> Char -> State, State -> Bool) | |
| 9 type ListDA = (State, [((State, Char), State)], [State]) | |
| 10 | |
| 11 a :: DA | |
| 12 a = (0, delta, (==1)) | |
| 13 where | |
| 14 delta 0 'a' = 1 | |
| 15 delta 1 'a' = 1 | |
| 16 delta 2 'a' = 1 | |
| 17 delta 0 'b' = 2 | |
| 18 delta 1 'b' = 2 | |
| 19 delta 2 'b' = 2 | |
| 20 | |
| 21 toDA :: ListDA -> DA | |
| 22 toDA (start, delta, final) = (start, deltaFun delta, (`elem` final)) | |
| 23 where deltaFun dl = curry (fromMaybe 0 . flip lookup dl) | |
| 24 {- End Library -} | |
| 25 | |
| 26 | |
| 27 {---------------------------------------------------------------------} | |
| 28 {- Aufgabe G5.1 -} | |
| 29 | |
| 30 iter :: Int -> (a -> a) -> a -> a | |
| 13 | 31 iter n f x |
| 32 | n <= 0 = x | |
| 33 | otherwise = iter (n - 1) f (f x) | |
| 11 | 34 |
| 35 | |
| 36 pow :: Int -> Int -> Int | |
| 13 | 37 pow n k = iter k (\x -> x*n) 1 |
| 11 | 38 |
| 39 | |
| 40 drop' :: Int -> [a] -> [a] | |
| 13 | 41 drop' n xs = iter n tail xs |
| 11 | 42 |
| 43 | |
| 44 replicate' :: Int -> a -> [a] | |
| 13 | 45 replicate' n x = iter n (x:) [] |
| 11 | 46 |
| 47 | |
| 48 | |
| 49 {---------------------------------------------------------------------} | |
| 50 {- Aufgabe G5.2 -} | |
| 51 | |
| 13 | 52 {- Fold-Beispiel anhand der Summenfunktion -} |
| 53 | |
| 54 sum' :: [Integer] -> Integer | |
| 55 sum' [] = 0 | |
| 56 sum' (x:xs) = x + sum' xs | |
| 57 | |
| 58 | |
| 59 sum'' :: [Integer] -> Integer | |
| 60 sum'' xs = sum_acc xs 0 | |
| 61 where | |
| 62 sum_acc :: [Integer] -> Integer -> Integer | |
| 63 sum_acc [] acc = acc | |
| 64 sum_acc (x:xs) acc = sum_acc xs (x+acc) | |
| 65 | |
| 66 sum_fold :: [Integer] -> Integer | |
| 67 --sum_fold xs = foldr (\x acc -> x + acc) 0 xs | |
| 68 sum_fold xs = foldr (+) 0 xs | |
| 69 | |
| 70 {-----} | |
| 71 | |
| 11 | 72 partition_rec :: (a -> Bool) -> [a] -> ([a], [a]) |
| 13 | 73 partition_rec p xs = partition_rec' xs ([], []) |
| 74 where | |
| 75 partition_rec' [] (ts, fs) = (reverse ts, reverse fs) | |
| 76 partition_rec' (x:xs) (ts, fs) = | |
| 77 if p x then partition_rec' xs (x:ts, fs) | |
| 78 else partition_rec' xs (ts, x:fs) | |
| 11 | 79 |
| 80 | |
|
12
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
81 partition_foldr :: (a -> Bool) -> [a] -> ([a], [a]) |
| 13 | 82 partition_foldr p xs = foldr partition_foldr' ([], []) xs |
| 83 where | |
| 84 partition_foldr' x (ts, fs) = | |
| 85 if p x then (x:ts, fs) | |
| 86 else (ts, x:fs) | |
| 11 | 87 |
| 88 | |
| 89 partition_filter :: (a -> Bool) -> [a] -> ([a], [a]) | |
| 13 | 90 --partition_filter p xs = (filter p xs, filter (\x -> not(p(x))) xs) |
| 91 partition_filter p xs = (filter p xs, filter (not . p) xs) | |
| 92 | |
| 93 | |
| 94 prop_partition_foldr_even xs = | |
| 95 partition_foldr even xs == partition even xs | |
| 96 | |
| 97 | |
| 98 prop_partition_distrib_even xs ys = | |
| 99 partition even (xs ++ ys) == (ts ++ ts', fs ++ fs') | |
| 100 where | |
| 101 (ts, fs) = partition even xs | |
| 102 (ts', fs') = partition even ys | |
| 11 | 103 |
| 104 | |
| 105 zipWith' :: (a -> b -> c) -> [a] -> [b] -> [c] | |
| 13 | 106 zipWith' _ [] [] = [] |
| 107 zipWith' f (x:xs) (y:ys) = (f x y) : zipWith' f xs ys | |
| 11 | 108 |
| 109 | |
| 110 | |
| 111 {---------------------------------------------------------------------} | |
|
12
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
112 {- Aufgabe G5.3 -} |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
113 |
| 13 | 114 -- Beide Identitäten |
|
12
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
115 lambda_1 = (\xs -> foldr (++) [] (map (\x -> [x]) xs)) |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
116 lambda_2 = (\gg xx yy -> head (tail (zipWith gg [ xx , xx ] [ yy , yy ]))) |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
117 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
118 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
119 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
120 {---------------------------------------------------------------------} |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
121 {- Aufgabe G5.4 -} |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
122 |
| 13 | 123 -- Unendliche Liste mit Nullen |
|
12
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
124 zeros :: [Int] |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
125 zeros = 0 : zeros |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
126 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
127 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
128 length' :: [a] -> Int |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
129 length' [] = 0 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
130 length' (_:xs) = 1 + length' xs |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
131 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
132 |
| 13 | 133 -- Terminiert immer. |
| 134 -- m <= n: 0 | |
| 135 -- m > n: 1 | |
|
12
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
136 h :: Integer -> Integer -> Integer |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
137 h m n |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
138 | m == n = 0 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
139 | m < n = h m (n - 1) |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
140 | m >= n = h n m + 1 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
141 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
142 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
143 |
|
8496af3b866b
add G5.3 and G5.4 definitions
Markus Kaiser <markus.kaiser@in.tum.de>
parents:
11
diff
changeset
|
144 {---------------------------------------------------------------------} |
| 11 | 145 {- Aufgabe H5.1 -} |
| 146 | |
| 147 fixpoint :: (a -> a -> Bool) -> (a -> a) -> a -> a | |
| 148 fixpoint = undefined | |
| 149 | |
| 150 | |
| 151 cents :: [Integer] -> [Integer] | |
| 152 cents = undefined | |
| 153 | |
| 154 | |
| 155 trancl :: [(Integer, Integer)] -> [(Integer, Integer)] | |
| 156 trancl = undefined | |
| 157 | |
| 158 | |
| 159 | |
| 160 {---------------------------------------------------------------------} | |
| 161 {- Aufgabe H5.2 -} | |
| 162 | |
| 163 advance :: DA -> State -> String -> State | |
| 164 advance = undefined | |
| 165 | |
| 166 | |
| 167 prop_advance_empty :: ListDA -> State -> Bool | |
| 168 prop_advance_empty = undefined | |
| 169 | |
| 170 | |
| 171 prop_advance_single :: ListDA -> State -> Char -> Bool | |
| 172 prop_advance_single = undefined | |
| 173 | |
| 174 | |
| 175 prop_advance_concat :: ListDA -> State -> String -> String -> Bool | |
| 176 prop_advance_concat = undefined | |
| 177 | |
| 178 | |
| 179 accept :: DA -> String -> Bool | |
| 180 accept = undefined | |
| 181 | |
| 182 | |
| 183 reachableStates :: DA -> State -> [Char] -> [State] | |
| 184 reachableStates = undefined | |
| 185 | |
| 186 | |
| 187 | |
| 188 {---------------------------------------------------------------------} | |
| 189 {- Aufgabe H5.3 -} | |
| 190 | |
| 191 {-WETT-} | |
| 192 quasiSubseq :: Eq a => [a] -> [a] -> Bool | |
| 193 quasiSubseq xs ys = undefined | |
| 194 {-TTEW-} |