1 files changed, 82 insertions, 79 deletions

diff --git a/AufgabeFFP8.hs b/AufgabeFFP8.hs
index 9d244e6..436e6cb 100644
--- a/AufgabeFFP8.hs
+++ b/AufgabeFFP8.hs
@@ -1,20 +1,22 @@
 module AufgabeFFP8
 where
 
-import Data.Char
 import Data.Array
-import Data.List hiding ((\\), insert, delete, sort)
+import Data.List hiding ((\\))
 import Test.QuickCheck
 
-type Nat = [Int]
+type Nat = Int
 
-(\\) :: Eq a => [a] -> [a] -> [a]
-xs \\ ys = filter (\x -> x `notElem` ys) xs
+-- Minfree basic version
 
 minfree_bv :: [Int] -> Int
 minfree_bv xs = head ([0..] \\ xs)
 
--- checklist
+(\\) :: Eq a => [a] -> [a] -> [a]
+xs \\ ys = filter (\x -> x `notElem` ys) xs
+
+-- Minfree checklist
+
 minfree_chl :: [Int] -> Int
 minfree_chl = search . checklist
 
@@ -22,95 +24,97 @@ 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
-
--- countlist
+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
+minfree_col = search0 . assocs . 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
-
--- unused
+countlist xs = accumArray (+) 0 (0,n) (zip xs (repeat 1))
+  where n = length xs
+  
 sort :: [Int] -> [Int]
-sort xs = concat [replicate k x | (x, k) <- assocs ( countlist xs ) ]
+sort xs = concat [replicate k x | (x,k) <- assocs $ countlist xs]
 
-search_countlist :: Array Int Int -> Int
-search_countlist = length . takeWhile (/= 0) . elems
+search0 :: [(Int, Int)] -> Int
+search0 [] = -1
+search0((i,0):_) = i
+search0 (x:xs) = search0 xs
+
+-- minfree basic daq
 
--- basic divide-and-conquer
 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
-
--- refined divide-and-conquer
+minfree_b xs = if (null ([0..b-1] \\ us))
+    then (head ([b..] \\ vs))
+    else (head ([0..] \\ us))
+    where
+      b = 1 + (length xs) `div` 2
+      (us, vs) = partition (<b) xs
+      
+-- minfree refined daq
+
 minfree_r :: [Int] -> Int
-minfree_r xs = minfrom 0 xs
-
-minfrom :: Int -> [Int] -> Int
-minfrom a xs
-        | null xs = a
-        | length us == b-a = minfrom b vs
-        | otherwise = minfrom a us
-        where
-        (us, vs) = partition (<b) xs
-        b = a + 1 + (length xs) `div` 2
-
--- optimised divide-and-conquer
+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 b 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
-
+  | 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
 
--- from slide 154
-divideAndConquer :: (p -> Bool) -> (p -> s) -> (p -> [p]) -> (p -> [s] -> s) -> p -> s
+divideAndConquer :: (p->Bool) -> (p->s) ->(p-> [p]) -> (p-> [s] -> s)-> p -> s
 divideAndConquer indiv solve divide combine initPb = dAC initPb
-  where
+  where 
     dAC pb
-      | indiv pb = solve pb
+      | indiv pb  = solve pb
       | otherwise = combine pb (map dAC (divide pb))
-
-
-
--- basic divide-and-conquer mittels higher order function
+      
+-- 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 xs = divideAndConquer b_indiv b_solve b_divide b_combine (length xs, xs)
-
-b_indiv :: (Int, [Int]) -> Bool
-b_indiv (0, _) = True -- empty list
-b_indiv (n, xs) = n /= length xs -- only divide on first call
-
-b_solve :: (Int, [Int]) -> Int
-b_solve (n, xs) = head $ [n..] \\ xs
-
-b_divide :: (Int, [Int]) -> [ (Int, [Int]) ]
-b_divide (n, xs) = [(0, us), (b, vs)]
-        where
-        b = 1 + (length xs) `div` 2
-        (us, vs) = partition (<b) xs
-
-b_combine :: (Int, [Int]) -> [Int] -> Int
-b_combine xs sols = head sols
+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
                                                                         
 
 -- refined divide-and-conquer mittels higher order function
@@ -154,5 +158,4 @@ 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)
-
+prop_allImplsEq_b xs = all (>=0) xs ==> all_eq $ calc_all (nub xs)
\ No newline at end of file