From 18d2290d762a1064b089b91dc2887367592778eb Mon Sep 17 00:00:00 2001
From: manuel <manuel@mausz.at>
Date: Sun, 20 May 2012 17:48:47 +0200
Subject: implement part 1 of part 2 of exercise 7

---
 AufgabeFFP7.hs | 42 ++++++++++++++++++++++++++++++++++++++----
 1 file changed, 38 insertions(+), 4 deletions(-)

diff --git a/AufgabeFFP7.hs b/AufgabeFFP7.hs
index 9d05db3..9337010 100644
--- a/AufgabeFFP7.hs
+++ b/AufgabeFFP7.hs
@@ -1,6 +1,8 @@
 module AufgabeFFP7
 where
 
+import List hiding ((\\))
+
 type Buffer = (Int, String)
 
 -- the empty buffer
@@ -59,10 +61,42 @@ type BufferI = (String, String)
 
 --------------------------------------------------------------------------------
 
---TODO ssfn ::
---TODO sap ::
---TODO minfree ::
---TODO removeDuplicates ::
+-- from slide 154
+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))
+
+-- from slide 156
+quickSort :: Ord a => [a] -> [a]
+quickSort lst = divideAndConquer indiv solve divide combine lst
+  where
+    indiv ls = length ls <= 1
+    solve = id
+    divide (l:ls) = [[ x | x <- ls, x <= l], [ x | x <- ls, x > l] ]
+    combine (l:_) [l1,l2] = l1 ++ [l] ++ l2
+
+removeDuplicates :: [Integer] -> [Integer]
+removeDuplicates xs = nub xs
+
+-- from slide 245
+ssfn :: [Integer] -> Integer
+ssfn = (sap 0) . removeDuplicates . quickSort
+
+sap :: Integer -> [Integer] -> Integer
+sap n [] = 0
+sap n (x:xs)
+  | n /= x = n
+  | otherwise = sap (n+1) xs
+
+-- from slide 247
+(\\) :: Eq a => [a] -> [a] -> [a]
+xs \\ ys = filter (\x -> x `notElem` ys) xs
+
+minfree :: [Int] -> Int
+minfree xs = head ([0..] \\ xs)
 
 --------------------------------------------------------------------------------
 
-- 
cgit v1.2.3