1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
|
module AufgabeFFP5
where
import Data.Array
newtype Table a b = Tbl (Array b a)
deriving Show
newTable :: (Ix b) => [(b, a)] -> Table a b
newTable l = Tbl (array (lo, hi) l)
where
indices = map fst l
lo = minimum indices
hi = maximum indices
findTable :: (Ix b) => Table a b -> b -> a
findTable (Tbl a) i = a ! i
updTable :: (Ix b) => (b, a) -> Table a b -> Table a b
updTable p@(i, x) (Tbl a) = Tbl (a // [p])
dynamic :: (Ix coord) => (Table entry coord -> coord -> entry) -> (coord, coord) -> (Table entry coord)
dynamic compute bnds = t
where
t = newTable (map (\coord -> (coord, compute t coord)) (range bnds))
-------------------------------------------------------------------------------
-- 1.
-------------------------------------------------------------------------------
bndsAS :: Array Int Int -> ((Int, Int), (Int, Int))
bndsAS a = ((l,l), (h,h))
where
(l,h) = bounds a
-- fill the table. Lower half below diagonal not necessary
-- but filled with the symmetric value
compAS :: Array Int Int -> Table Int (Int, Int) -> (Int, Int) -> Int
compAS a t (i,j)
| i == j = a ! j
| i<j = compAS a t (j,i)
| otherwise = findTable t (i-1, j) + a!i
-- computes distance-sum-table for array
asTbl :: Array Int Int -> Table Int (Int, Int)
asTbl a = dynamic (compAS a) (bndsAS a)
-- maximum function for tables
tblMax :: (Ord a, Ix b) => Table a b -> a
tblMax (Tbl a) = maximum $ elems a
-- maximum of the array's distance-sums
mas :: Array Int Int -> Int
mas a = tblMax $ asTbl a
-------------------------------------------------------------------------------
-- 2.
-------------------------------------------------------------------------------
-- all indices where the value equals to the maximum distance-sum
amas :: Array Int Int -> [(Int, Int)]
amas a = [(i,j) | ((i,j),v) <- (assocs array), i<=j, v>=maxAS]
where
t@(Tbl array) = asTbl a
maxAS = tblMax t
-------------------------------------------------------------------------------
-- 3.
-------------------------------------------------------------------------------
-- computes index with maximum index-difference
maxL :: [(Int, Int)] -> (Int, Int)
maxL [] = error "maximum of empty list"
maxL [x] = x
maxL (x:xs)
| l x >= l maxTail = x
| otherwise = maxTail
where
l (x,y) = y-x
maxTail = maxL xs
-- index with maximum distance-sum and maximum index-difference
lmas :: Array Int Int -> (Int, Int)
lmas a = maxL $ amas a
-------------------------------------------------------------------------------
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))
-------------------------------------------------------------------------------
-- 4.
-------------------------------------------------------------------------------
mi_indiv :: [a] -> Bool
mi_indiv a = length a <= 1
mi_solve :: (Ix a, Show a) => (b -> Bool) -> [(a,b)] -> [(a,b)]
mi_solve wf [(a,b)]
| wf b = [(a,b)]
| otherwise = []
mi_divide :: [a] -> [[a]]
mi_divide (x:xs) = [[x], xs]
mi_combine :: [a] -> [[a]] -> [a]
mi_combine _ [] = error "No matching index"
mi_combine a (x:xs)
| null x = mi_combine a xs
| otherwise = [head x]
minIndex :: (Ix a, Show a) => Array a b -> (b -> Bool) -> a
minIndex a wf = fst $ head $ divideAndConquer mi_indiv (mi_solve wf) mi_divide mi_combine $ assocs a
|
