|
2
|
1 module Exercise_2 where |
|
|
2 import Test.QuickCheck |
|
|
3 import Data.List |
|
|
4 |
|
|
5 {---------------------------------------------------------------------} |
|
|
6 {- Aufgabe G2.1 -} |
|
|
7 all_sums :: [Integer] -> [Integer] -> [Integer] |
|
5
|
8 all_sums xs ys = [x + y | x <- xs, y <- ys] |
|
2
|
9 |
|
|
10 |
|
|
11 evens :: [Integer] -> [Integer] |
|
5
|
12 evens xs = [x | x <- xs, even x] |
|
2
|
13 |
|
|
14 |
|
|
15 n_lists :: [Integer] -> [[Integer]] |
|
5
|
16 n_lists xs = [[1..x] | x <- xs] |
|
2
|
17 |
|
|
18 |
|
|
19 all_even_sum_lists :: [Integer] -> [Integer] -> [[Integer]] |
|
5
|
20 all_even_sum_lists xs ys = [[1..(x+y)] | x <- xs, y <- ys, even (x+y)] |
|
2
|
21 |
|
|
22 |
|
|
23 |
|
|
24 {---------------------------------------------------------------------} |
|
|
25 {- Aufgabe G2.2 -} |
|
5
|
26 union'' :: [Integer] -> [Integer] -> [Integer] |
|
|
27 union'' xs ys = xs ++ ys |
|
2
|
28 |
|
|
29 |
|
|
30 intersection :: [Integer] -> [Integer] -> [Integer] |
|
5
|
31 intersection xs ys = [x | x <- xs, x `elem` ys] |
|
|
32 -- Alternativ ohne elem: |
|
|
33 -- intersection xs ys = [x | x <- xs, y <- ys, x == y] |
|
2
|
34 |
|
|
35 |
|
|
36 diff :: [Integer] -> [Integer] -> [Integer] |
|
5
|
37 diff xs ys = [x | x <- xs, not(x `elem` ys)] |
|
2
|
38 |
|
|
39 |
|
|
40 elem' :: Integer -> [Integer] -> Bool |
|
5
|
41 elem' x xs = [y | y <- xs, y == x] /= [] |
|
2
|
42 |
|
|
43 |
|
|
44 union' :: [Integer] -> [Integer] -> [Integer] |
|
5
|
45 union' xs ys = diff xs ys ++ ys |
|
|
46 |
|
2
|
47 |
|
|
48 |
|
|
49 {---------------------------------------------------------------------} |
|
|
50 {- Aufgabe G2.3 -} |
|
|
51 eq_frac :: (Integer,Integer) -> (Integer,Integer) -> Bool |
|
5
|
52 eq_frac (a,b) (c,d) = a * d == c * b |
|
2
|
53 |
|
|
54 |
|
|
55 intersection_frac :: [(Integer,Integer)] -> [(Integer,Integer)] -> [(Integer,Integer)] |
|
5
|
56 intersection_frac xs ys = [x | x <- xs, y <- ys, x `eq_frac` y] |
|
2
|
57 |
|
|
58 |
|
|
59 |
|
|
60 {---------------------------------------------------------------------} |
|
|
61 {- Aufgabe G2.4 -} |
|
|
62 pow2_slow :: Integer -> Integer |
|
|
63 pow2_slow 0 = 1 |
|
|
64 pow2_slow n | n > 0 = 2 * pow2_slow (n - 1) |
|
|
65 |
|
|
66 |
|
|
67 pow2 :: Integer -> Integer |
|
5
|
68 pow2 0 = 1 |
|
|
69 pow2 n |
|
|
70 | n < 0 = error "Postive n only" |
|
|
71 | even n = pow2 (n `div` 2) ^ 2 |
|
|
72 | otherwise = 2 * pow2 (n - 1) |
|
2
|
73 |
|
|
74 |
|
|
75 |
|
|
76 {---------------------------------------------------------------------} |
|
|
77 {- Aufgabe G2.5 -} |
|
|
78 reachable :: [(Integer, Integer)] -> Integer -> [(Integer, Integer)] |
|
5
|
79 reachable graph 0 = nub $ concat [[(u, u), (v, v)] | (u, v) <- graph] |
|
|
80 reachable graph 1 = graph |
|
|
81 reachable graph n | n > 0 = [(u, x) | (u, v) <- graph, (w, x) <- reachable graph (n-1), v == w] |
|
2
|
82 |
|
|
83 |
|
|
84 |
|
|
85 {---------------------------------------------------------------------} |
|
|
86 {- Aufgabe H2.1 -} |
|
10
|
87 factorial :: Integer -> Integer |
|
|
88 factorial 0 = 1 |
|
|
89 factorial n = n * factorial (n - 1) |
|
|
90 |
|
2
|
91 factorials :: [Integer] -> [Integer] |
|
10
|
92 factorials ns = [factorial n | n <- ns, n >= 0] |
|
|
93 |
|
|
94 prop_factorialsDistrib cs cs' = |
|
|
95 factorials (cs ++ cs') == factorials cs ++ factorials cs' |
|
|
96 prop_factorialsOne n = factorials [n] == (if n < 0 then [] else [factorial n]) |
|
|
97 prop_factorialsNil = factorials [] == [] |
|
2
|
98 |
|
5
|
99 |
|
2
|
100 count :: [Char] -> Char -> Integer |
|
10
|
101 count cs c = genericLength [c' | c' <- cs, c' == c] |
|
|
102 |
|
|
103 count' :: [Char] -> Char -> Integer |
|
|
104 count' cs c = sum [1 | c' <- cs, c' == c] |
|
2
|
105 |
|
|
106 |
|
|
107 |
|
|
108 {---------------------------------------------------------------------} |
|
|
109 {- Aufgabe H2.2 -} |
|
|
110 lookupTab :: [Integer] -> [(Integer, [Char])] -> [[[Char]]] |
|
10
|
111 lookupTab keys tab = [[v | (k,v) <- tab, key == k] | key <- keys] |
|
2
|
112 |
|
|
113 |
|
|
114 |
|
|
115 {---------------------------------------------------------------------} |
|
|
116 {- Aufgabe H2.3 -} |
|
|
117 wordsOfLength :: [Char] -> Integer -> [[Char]] |
|
10
|
118 wordsOfLength alphabet 0 = [[]] |
|
|
119 wordsOfLength alphabet n = [[a] ++ s | a <- alphabet, s <- wordsOfLength alphabet (n - 1)] |
|
2
|
120 |
|
|
121 |
|
|
122 |
|
|
123 {---------------------------------------------------------------------} |
|
|
124 {- Aufgabe H2.4 -} |
|
|
125 perms :: [Char] -> [[Char]] |
|
10
|
126 perms xs | xs == "" = [""] |
|
|
127 | otherwise = |
|
|
128 reverse (sort (nub ([ys ++ [y] | |
|
|
129 y <- xs, ys <- perms (delete y xs)]))) |
|
|
130 |
|
|
131 perms' :: [Char] -> [[Char]] |
|
|
132 perms' "" = [""] |
|
|
133 perms' xs = [ys ++ [y] | y <- sort $ nub xs, ys <- perms' $ delete y xs] |
|
|
134 |
|
|
135 perms'' :: [Char] -> [[Char]] |
|
|
136 perms'' "" = [""] |
|
|
137 perms'' xs = reverse [y : ys | y <- sort $ nub xs, ys <- perms'' $ delete y xs] |
