summaryrefslogtreecommitdiffstats
path: root/AufgabeFFP5.hs
diff options
context:
space:
mode:
Diffstat (limited to 'AufgabeFFP5.hs')
-rw-r--r--AufgabeFFP5.hs30
1 files changed, 15 insertions, 15 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