Bsp 8.1

1 files changed, 119 insertions, 0 deletions

diff --git a/AufgabeFFP8.hs b/AufgabeFFP8.hs
new file mode 100644
index 0000000..2747597
--- /dev/null
+++ b/AufgabeFFP8.hs
@@ -0,0 +1,119 @@
+module AufgabeFFP8
+where
+
+import Data.Array
+import Data.List hiding ((\\))
+import Test.QuickCheck
+
+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 = search0 . assocs . countlist
+
+countlist :: [Int] -> Array Int Int
+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]
+
+search0 :: [(Int, Int)] -> Int
+search0 [] = -1
+search0((i,0):_) = i
+search0 (x:xs) = search0 xs
+
+-- 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
+      b = 1 + (length xs) `div` 2
+      (us, vs) = partition (<b) xs
+      
+-- 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 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
+    
+-- 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 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
+
+