diff options
Diffstat (limited to 'AufgabeFFP5.hs')
| -rw-r--r-- | AufgabeFFP5.hs | 30 |
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 @@ | |||
| 1 | module AufgabeFFP5 | 1 | module AufgabeFFP5 |
| 2 | where | 2 | where |
| 3 | 3 | ||
| 4 | import Data.Array | 4 | import Data.Array |
| 5 | 5 | ||
| 6 | newtype Table a b = Tbl (Array b a) | 6 | newtype Table a b = Tbl (Array b a) |
| 7 | deriving Show | 7 | deriving Show |
| 8 | 8 | ||
| @@ -31,7 +31,7 @@ dynamic compute bnds = t | |||
| 31 | bndsAS :: Array Int Int -> ((Int, Int), (Int, Int)) | 31 | bndsAS :: Array Int Int -> ((Int, Int), (Int, Int)) |
| 32 | bndsAS a = ((l,l), (h,h)) | 32 | bndsAS 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 |
| 45 | asTbl :: Array Int Int -> Table Int (Int, Int) | 45 | asTbl :: Array Int Int -> Table Int (Int, Int) |
| 46 | asTbl a = dynamic (compAS a) (bndsAS a) | 46 | asTbl a = dynamic (compAS a) (bndsAS a) |
| 47 | 47 | ||
| 48 | -- maximum function for tables | 48 | -- maximum function for tables |
| 49 | tblMax :: (Ord a, Ix b) => Table a b -> a | 49 | tblMax :: (Ord a, Ix b) => Table a b -> a |
| 50 | tblMax (Tbl a) = maximum $ elems a | 50 | tblMax (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 |
| 83 | lmas :: Array Int Int -> (Int, Int) | 83 | lmas :: Array Int Int -> (Int, Int) |
| 84 | lmas a = maxL $ amas a | 84 | lmas 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 | ||
| 100 | mi_indiv :: [a] -> Bool | 100 | mi_indiv :: [a] -> Bool |
| 101 | miIndiv a = length a <= 1 | 101 | mi_indiv a = length a <= 1 |
| 102 | 102 | ||
| 103 | mi_solve :: (Ix a, Show a) => (b -> Bool) -> [(a,b)] -> [(a,b)] | 103 | mi_solve :: (Ix a, Show a) => (b -> Bool) -> [(a,b)] -> [(a,b)] |
| 104 | miSolve wf [(a,b)] | 104 | mi_solve wf [(a,b)] |
| 105 | | wf b = [(a,b)] | 105 | | wf b = [(a,b)] |
| 106 | | otherwise = [] | 106 | | otherwise = [] |
| 107 | 107 | ||
| 108 | mi_divide :: [a] -> [[a]] | 108 | mi_divide :: [a] -> [[a]] |
| 109 | miDivide (x:xs) = [[x], xs] | 109 | mi_divide (x:xs) = [[x], xs] |
| 110 | 110 | ||
| 111 | mi_combine :: [a] -> [[a]] -> [a] | 111 | mi_combine :: [a] -> [[a]] -> [a] |
| 112 | miCombine _ [] = error "No matching index" | 112 | mi_combine _ [] = error "No matching index" |
| 113 | miCombine a (x:xs) | 113 | mi_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 | ||
| 117 | minIndex :: (Ix a, Show a) => Array a b -> (b -> Bool) -> a | 117 | minIndex :: (Ix a, Show a) => Array a b -> (b -> Bool) -> a |
| 118 | minIndex a wf = fst $ head $ divideAndConquer miIndiv (miSolve wf) miDivide miCombine $ assocs a \ No newline at end of file | 118 | minIndex a wf = fst $ head $ divideAndConquer mi_indiv (mi_solve wf) mi_divide mi_combine $ assocs a |
