summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
-rw-r--r--AufgabeFFP5.hs30
-rw-r--r--TestAufgabeFFP5.hs7
2 files changed, 18 insertions, 19 deletions
diff --git a/AufgabeFFP5.hs b/AufgabeFFP5.hs
index 430fb22..75383f7 100644
--- a/AufgabeFFP5.hs
+++ b/AufgabeFFP5.hs
@@ -1,8 +1,8 @@
1module AufgabeFFP5 1module AufgabeFFP5
2where 2where
3 3
4import Data.Array 4import Data.Array
5 5
6newtype Table a b = Tbl (Array b a) 6newtype Table a b = Tbl (Array b a)
7 deriving Show 7 deriving Show
8 8
@@ -31,7 +31,7 @@ dynamic compute bnds = t
31bndsAS :: Array Int Int -> ((Int, Int), (Int, Int)) 31bndsAS :: Array Int Int -> ((Int, Int), (Int, Int))
32bndsAS a = ((l,l), (h,h)) 32bndsAS a = ((l,l), (h,h))
33 where 33 where
34 (l,h) = bounds a 34 (l,h) = bounds a
35 35
36-- fill the table. Lower half below diagonal not necessary 36-- fill the table. Lower half below diagonal not necessary
37-- but filled with the symmetric value 37-- but filled with the symmetric value
@@ -44,7 +44,7 @@ compAS a t (i,j)
44-- computes distance-sum-table for array 44-- computes distance-sum-table for array
45asTbl :: Array Int Int -> Table Int (Int, Int) 45asTbl :: Array Int Int -> Table Int (Int, Int)
46asTbl a = dynamic (compAS a) (bndsAS a) 46asTbl a = dynamic (compAS a) (bndsAS a)
47 47
48-- maximum function for tables 48-- maximum function for tables
49tblMax :: (Ord a, Ix b) => Table a b -> a 49tblMax :: (Ord a, Ix b) => Table a b -> a
50tblMax (Tbl a) = maximum $ elems a 50tblMax (Tbl a) = maximum $ elems a
@@ -79,7 +79,7 @@ maxL (x:xs)
79 l (x,y) = y-x 79 l (x,y) = y-x
80 maxTail = maxL xs 80 maxTail = maxL xs
81 81
82-- index with maximum distance-sum and maximum index-difference 82-- index with maximum distance-sum and maximum index-difference
83lmas :: Array Int Int -> (Int, Int) 83lmas :: Array Int Int -> (Int, Int)
84lmas a = maxL $ amas a 84lmas a = maxL $ amas a
85 85
@@ -92,27 +92,27 @@ divideAndConquer indiv solve divide combine initPb = dAC initPb
92 | indiv pb = solve pb 92 | indiv pb = solve pb
93 | otherwise = combine pb (map dAC (divide pb)) 93 | otherwise = combine pb (map dAC (divide pb))
94 94
95 95
96------------------------------------------------------------------------------- 96-------------------------------------------------------------------------------
97-- 4. 97-- 4.
98------------------------------------------------------------------------------- 98-------------------------------------------------------------------------------
99 99
100mi_indiv :: [a] -> Bool 100mi_indiv :: [a] -> Bool
101miIndiv a = length a <= 1 101mi_indiv a = length a <= 1
102 102
103mi_solve :: (Ix a, Show a) => (b -> Bool) -> [(a,b)] -> [(a,b)] 103mi_solve :: (Ix a, Show a) => (b -> Bool) -> [(a,b)] -> [(a,b)]
104miSolve wf [(a,b)] 104mi_solve wf [(a,b)]
105 | wf b = [(a,b)] 105 | wf b = [(a,b)]
106 | otherwise = [] 106 | otherwise = []
107 107
108mi_divide :: [a] -> [[a]] 108mi_divide :: [a] -> [[a]]
109miDivide (x:xs) = [[x], xs] 109mi_divide (x:xs) = [[x], xs]
110 110
111mi_combine :: [a] -> [[a]] -> [a] 111mi_combine :: [a] -> [[a]] -> [a]
112miCombine _ [] = error "No matching index" 112mi_combine _ [] = error "No matching index"
113miCombine a (x:xs) 113mi_combine a (x:xs)
114 | null x = miCombine a xs 114 | null x = mi_combine a xs
115 | otherwise = [head x] 115 | otherwise = [head x]
116 116
117minIndex :: (Ix a, Show a) => Array a b -> (b -> Bool) -> a 117minIndex :: (Ix a, Show a) => Array a b -> (b -> Bool) -> a
118minIndex a wf = fst $ head $ divideAndConquer miIndiv (miSolve wf) miDivide miCombine $ assocs a \ No newline at end of file 118minIndex a wf = fst $ head $ divideAndConquer mi_indiv (mi_solve wf) mi_divide mi_combine $ assocs a
diff --git a/TestAufgabeFFP5.hs b/TestAufgabeFFP5.hs
index 7e0b731..865f503 100644
--- a/TestAufgabeFFP5.hs
+++ b/TestAufgabeFFP5.hs
@@ -32,7 +32,7 @@ cases1 = "mas" ~: TestList [
32 "mas d" ~: 21 ~=? (mas d), 32 "mas d" ~: 21 ~=? (mas d),
33 "mas minA" ~: 0 ~=? (mas minA) 33 "mas minA" ~: 0 ~=? (mas minA)
34 ] 34 ]
35 35
36cases2 = TestLabel "amas" $ TestList [ 36cases2 = TestLabel "amas" $ TestList [
37 "amas a" ~: [(3,7), (4,7)] ~=? (amas a), 37 "amas a" ~: [(3,7), (4,7)] ~=? (amas a),
38 "amas b" ~: [(1,7),(1,8),(4,7),(4,8)] ~=? (amas b), 38 "amas b" ~: [(1,7),(1,8),(4,7),(4,8)] ~=? (amas b),
@@ -40,7 +40,7 @@ cases2 = TestLabel "amas" $ TestList [
40 "amas d" ~: [(2,6)] ~=? (amas d), 40 "amas d" ~: [(2,6)] ~=? (amas d),
41 "amas minA" ~: [(0,0)] ~=? (amas minA) 41 "amas minA" ~: [(0,0)] ~=? (amas minA)
42 ] 42 ]
43 43
44cases3 = TestLabel "lmas" $ TestList [ 44cases3 = TestLabel "lmas" $ TestList [
45 "lmas a" ~: (3,7) ~=? (lmas a), 45 "lmas a" ~: (3,7) ~=? (lmas a),
46 "lmas b" ~: (1,8) ~=? (lmas b), 46 "lmas b" ~: (1,8) ~=? (lmas b),
@@ -48,7 +48,7 @@ cases3 = TestLabel "lmas" $ TestList [
48 "lmas d" ~: (2,6) ~=? (lmas d), 48 "lmas d" ~: (2,6) ~=? (lmas d),
49 "lmas minA" ~: (0,0) ~=? (lmas minA) 49 "lmas minA" ~: (0,0) ~=? (lmas minA)
50 ] 50 ]
51 51
52cases4 = TestLabel "minIndex" $ TestList [ 52cases4 = TestLabel "minIndex" $ TestList [
53 "minIndex a (>5)" ~: 4 ~=? (minIndex a (>5)), 53 "minIndex a (>5)" ~: 4 ~=? (minIndex a (>5)),
54 "minIndex a (<0)" ~: 2 ~=? (minIndex a (<0)), 54 "minIndex a (<0)" ~: 2 ~=? (minIndex a (<0)),
@@ -62,7 +62,6 @@ cases4 = TestLabel "minIndex" $ TestList [
62 -- "minIndex w (=='swim')" ~: error "No matching index" ~=? (minIndex w (=="swim")) 62 -- "minIndex w (=='swim')" ~: error "No matching index" ~=? (minIndex w (=="swim"))
63 ] 63 ]
64 64
65
66tests :: [Test] 65tests :: [Test]
67tests = [cases1, cases2, cases3, cases4] 66tests = [cases1, cases2, cases3, cases4]
68 67