Making change with minimum denominations with memoization

Question

I was wondering how to make efficient algorithm with memoization. Particularly, is there a way to make O(1) access time for index value in Haskell?

Here is the problem described in detail. And here is my attempt for recursive algorithm:

denom :: (Int, Int) -> [Int] -> Int
denom (_, 0) _ = 0
denom (0, _) _ = (maxBound :: Int) - 1000 -- subtracting 1000 otherwise overflows
denom (i, j) di
  | v > j = denom (i-1, j) di
  | otherwise = min (denom (i-1, j) di) (1 + denom (i, j-v) di)
  where v = di !! (i - 1)

Also, how would I declare INFINITY in Haskell so that min works in all cases?

Answer 1

First off, to do O(1) access in Haskell, the standard go-to library is Data.Array.

Second, the general way to define something near a type but somehow "outside" it is to use the Maybe type; this is what I recommend for INFINITY. Also, I think that this makes more sense in the algorithm, because INFINITY really means "we can't make this value with this set of denominations", not "we can make this value with an infinite number of coins".

So using Maybe, the first thing we'll want to define is a version of min that works on Maybe Int:

myMin :: Ord a => Maybe a -> Maybe a -> Maybe a
myMin (Just a) (Just b) = Just $ min a b
myMin Nothing x = x
myMin x Nothing = x

Then, using that we can attack this problem using the algorithm given in the linked page:

minCoinCoint :: Int -> [Int] -> Maybe Int
minCoinCoint target denoms = res (target, length denoms)
  where
    denomArray = listArray (0, length denoms) (0:denoms)
    myArrayBounds = ((0, 0), (target, length denoms))
    myArray = array myArrayBounds [(i, res i) | i <- range myArrayBounds]
    res (_, 0) = Nothing
    res (0, _) = Just 0
    res (t, d) = let dval = denomArray ! d
                     prev1 = myArray ! (t, d-1)
                     prev2 = if t >= dval
                             then (+1) <$> (myArray ! (t-dval, d))
                             else Nothing
                 in myMin prev1 prev2

And that's it. (well, assuming you remember the import Data.Array line at the top of the file)

Note that myArray is built by referring to res, and res makes all of its recursive calls by finding values in myArray.

This syntax might be a bit confusing:

(+1) <$> (myArray ! (t-dval, d))

That's done because remember that each element of myArray isn't an Int but rather a Maybe Int. That syntax says "apply the function (+1) to the inside of the value (myArray ! (t-dval, d))", so that a Just 4 will become a Just 5, but a Nothing will remain a Nothing.