1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
|
module AufgabeFFP8
where
import Data.Array
import Data.List hiding ((\\))
import Test.QuickCheck
import Debug.Trace
type Nat = Int
-- Minfree basic version
minfree_bv :: [Int] -> Int
minfree_bv xs = head ([0..] \\ xs)
(\\) :: Eq a => [a] -> [a] -> [a]
xs \\ ys = filter (\x -> x `notElem` ys) xs
-- Minfree checklist
minfree_chl :: [Int] -> Int
minfree_chl = search . checklist
search :: Array Int Bool -> Int
search = length . takeWhile id . elems
checklist :: [Int] -> Array Int Bool
checklist xs = accumArray (||) False (0,n)
(zip (filter (<=n) xs) (repeat True))
where n = length xs
-- minfree countlist
minfree_col :: [Int] -> Int
minfree_col = search_countlist . countlist
countlist :: [Int] -> Array Int Int
countlist xs = accumArray (+) 0 (0, n) (zip xs (repeat 1))
where n = safe_maximum xs
safe_maximum :: [Int] -> Int
safe_maximum [] = 0
safe_maximum xs = maximum xs
search_countlist :: Array Int Int -> Int
search_countlist = length . takeWhile (/= 0) . elems
-- minfree basic daq
minfree_b :: [Int] -> Int
minfree_b xs = if (null ([0..b-1] \\ us))
then (head ([b..] \\ vs))
else (head ([0..] \\ us))
where
(us, vs) = partition (<b) xs
b = 1 + (length xs) `div` 2
-- minfree refined daq
minfree_r :: [Int] -> Int
minfree_r = minfrom_r 0
minfrom_r :: Nat -> [Nat] -> Nat
minfrom_r a xs
| null xs = a
| length us == b-a = minfrom_r b vs
| otherwise = minfrom_r a us
where
b = a + 1 + (length xs) `div` 2
(us, vs) = partition (<b) xs
-- minfree optimized daq (p262)
minfree_o :: [Int] -> Int
minfree_o xs = minfrom_o 0 (length xs, xs)
minfrom_o :: Int -> (Int, [Int]) -> Int
minfrom_o a (n, xs)
| n == 0 = a
| m == b-a = minfrom_o b (n-m, vs)
| otherwise = minfrom_o a (m, us)
where
(us,vs) = partition (<b) xs
b = a + 1 + n `div` 2
m = length us
-- true daq implementations
divideAndConquer :: (p->Bool) -> (p->s) ->(p-> [p]) -> (p-> [s] -> s)-> p -> s
divideAndConquer indiv solve divide combine initPb = dAC initPb
where
dAC pb
| indiv pb = solve pb
| otherwise = combine pb (map dAC (divide pb))
-- minfree basic daq higher order
b_indiv :: Int -> [Int] -> Bool
b_indiv l xs = length xs < l
b_solve :: [Int] -> [Int]
b_solve = id
b_divide :: Int -> [Int] -> [[Int]]
b_divide b xs = [us, vs]
where (us,vs) = partition (<b) xs
b_combine :: Int -> [Int] -> [[Int]] -> [Int]
b_combine b _ (us:vs:[]) = if (null ([0..b-1] \\ us))
then ([b..] \\ vs)
else ([0..] \\ us)
minfree_bhof :: [Int] -> Int
minfree_bhof [] = 0
minfree_bhof xs = head $ divideAndConquer (b_indiv (length xs)) b_solve (b_divide b) (b_combine b) xs
where b = 1+(length xs) `div` 2
-- minfree refined daq higher order
r_indiv :: (Int, [Int]) -> Bool
r_indiv (a, []) = True
r_indiv _ = False
r_solve :: (Int, [Int]) -> Int
r_solve (a, []) = a
r_divide :: (Int, [Int]) -> [(Int, [Int])]
r_divide (a, xs)
| length smaller == b-a = [(b, bigger)]
| otherwise = [(a, smaller)]
where
b = a + 1 + (length xs) `div` 2
(smaller, bigger) = partition (<b) xs
r_combine :: (Int, [Int]) -> [Int] -> Int
r_combine _ (a:[]) = a
minfree_rhof :: [Int] -> Int
minfree_rhof xs = divideAndConquer r_indiv r_solve r_divide r_combine (0, xs)
-- minfree optimized daq higher order
o_indiv :: (Int, Int, [Int]) -> Bool
o_indiv (a, 0, []) = True
o_indiv _ = False
o_solve :: (Int, Int, [Int]) -> Int
o_solve (a, 0, []) = a
o_divide :: (Int, Int, [Int]) -> [(Int, Int, [Int])]
o_divide (a, n, xs)
| ls == b-a = [(b, length bigger, bigger)]
| otherwise = [(a, ls, smaller)]
where
b = a + 1 + n `div` 2
(smaller, bigger) = partition (<b) xs
ls = length smaller
o_combine :: (Int, Int, [Int]) -> [Int] -> Int
o_combine _ (a:[]) = a
minfree_ohof :: [Int] -> Int
minfree_ohof xs = divideAndConquer o_indiv o_solve o_divide o_combine (0, length xs, xs)
-- QuickCheck part
functions = [ minfree_bv, minfree_chl, minfree_col,
minfree_b, minfree_r, minfree_o,
minfree_bhof, minfree_rhof, minfree_ohof]
-- calc values of all function
calc_all :: [Int] -> [Int]
calc_all xs = [f xs | f <- functions ]
-- check if all values of a list are the same
all_eq :: [Int] -> Bool
all_eq (x:[]) = True
all_eq (x:y:xs)
| x == y = all_eq (y:xs)
| otherwise = False
-- check if a list contains no duplicates
--no_dups :: [Int] -> Bool
--no_dups [] = True
--no_dups (x:xs)
-- | x `elem` xs = False
-- | otherwise = no_dups xs
prop_allImplsEq_a :: [Int] -> Bool
prop_allImplsEq_a xs = all_eq $ calc_all (nub xs)
-- keine negativen listenelemented durch vorbedingung entfernt
prop_allImplsEq_b :: [Int] -> Property
prop_allImplsEq_b xs = all (>=0) xs ==> all_eq $ calc_all (nub xs)
|
