From 6d69381656125552d83a64a0c513ab87b94b712e Mon Sep 17 00:00:00 2001 From: manuel Date: Mon, 30 Apr 2012 11:18:24 +0200 Subject: adding datatype table needed for exercise 4 part 2 --- AufgabeFFP4.hs | 27 ++++++++++++++++++++++++--- 1 file changed, 24 insertions(+), 3 deletions(-) diff --git a/AufgabeFFP4.hs b/AufgabeFFP4.hs index 8e7cbf1..1521a5d 100644 --- a/AufgabeFFP4.hs +++ b/AufgabeFFP4.hs @@ -2,6 +2,7 @@ module AufgabeFFP4 where import List +import Data.Array type Weight = Int -- Gewicht type Value = Int -- Wert @@ -91,7 +92,27 @@ knapsack objects limit = (psol, v) ------------------------------------------------------------------------------- ---binomDyn :: (Integer, Integer) -> Integer ---binomDyn (m, n) = ... --- where ... dynamic compB... bndsB... +-- see lecture slide #207 ff. +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)) + +------------------------------------------------------------------------------- -- cgit v1.2.3