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
|
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))
-------------------------------------------------------------------------------
bndsAS :: Array Int Int -> ((Int, Int), (Int, Int))
bndsAS a = ((l,l), (h,h))
where
(l,h) = bounds a
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
asDyn :: Array Int Int -> (Int, Int) -> Int
asDyn a (i,j) = findTable t (i,j)
where
t = dynamic (compAS a) (bndsAS a)
-- maximum function for tables
tblMax :: Table Int (Int,Int) -> Int
tblMax (Tbl a) = maximum $ elems a
mas :: Array Int Int -> Int
mas a = tblMax $ dynamic (compAS a) (bndsAS a)
|
