From 46071eee81e180c0f9c2e413f5bec6fd613a7576 Mon Sep 17 00:00:00 2001
From: Matthias Wisniowski <matthias.wisniowski@gmail.com>
Date: Wed, 30 May 2012 02:04:00 +0200
Subject: minfree_ohof

---
 AufgabeFFP8.hs | 26 +++++++++++++++++++++++++-
 1 file changed, 25 insertions(+), 1 deletion(-)

diff --git a/AufgabeFFP8.hs b/AufgabeFFP8.hs
index fffc717..89c3a66 100644
--- a/AufgabeFFP8.hs
+++ b/AufgabeFFP8.hs
@@ -121,7 +121,7 @@ r_indiv (a, []) = True
 r_indiv _ = False
 
 r_solve :: (Int, [Int]) -> Int
-r_solve (a, _) = a
+r_solve (a, []) = a
 
 r_divide :: (Int, [Int]) -> [(Int, [Int])]
 r_divide (a, xs)
@@ -137,6 +137,30 @@ 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,
-- 
cgit v1.2.3