2 responses to “Exercise 5.9”

1. Here’s one way of solving the problem as described in the technical error, which finds the best way of doing it. It uses several functions from the Standard Prelude and a little bit of currying. Hopefully this will be properly formatted – apologies if not!

   type Coin = (Int,[Int])
   
   {-
    This takes a list of coins and produces a list of Coins, where each coin
    denomination is converted into a pair (value,[0,0,...,0,1,0,...]), where
    the value is the value of the coin, and the 0-1 array has length equal to
    the number of coins and has a 1 in only the ith position, where the coin
    is the ith in the list of coins (0-based), so for example, [10,5,1] will
    be converted to [ (10,[1,0,0]), (5,[0,1,0]), (1,[0,0,1]) ].
    In this way, we are easily able to add one coin to a collection, simply
    by adding the corresponding array termwise to the existing array.
   -}
   makeCoins :: [Int] -> [Coin]
   makeCoins coins = aux coins [0..]
                     where n = length coins
                           aux [] _ = []
                           aux (c:cs) (i:is) =
                             (c,replicate i 0 ++ [1] ++ replicate (n-1-i) 0):
                             aux cs is
   
   {- 
    This takes an amount and a set of coins, and recursively finds the best
    way of producing all amounts up to and including the given amount; this
    is the heart of the solution of the problem.
    We do this by finding all possibilities for making the required amount,
    which is easy: with a coin of value 10, say, we take the best way of making
    10 less (if the amount is at least 10), and add the array corresponding to
    the 10 coin to this best way.
    We then take the possibility which uses the fewest coins, using a variation
    on the Standard Prelude definition of minimum.
   -}
   best :: Int -> [Coin] -> [[Int]]
   best n coins
     | n == 0  = [ replicate (length coins) 0 ]
     | n > 0   = let bests = best (n-1) coins
                 in (next n coins bests) : bests
                   where next n coins bests
                           = let possibilities = concat (map aux coins)
                                 aux (den,coinList)
                                   = if den <= n
                                     then [ zipWith (+) (bests!!(den-1)) coinList ]
                                     else []
                             in smallest possibilities
                         smallest = foldr1 aux
                           where aux p1 p2 | (sum p1) <= (sum p2)  = p1
                                           | otherwise             = p2
   
   makeChange :: Int -> [Int] -> [Int]
   makeChange amt coins = let cs = makeCoins coins
                              bests = best amt cs
                          in head bests
   

2. We can do it with what we currently learnt (without scanl):
   
makeChange amt cs = zipWith div modList cs
where modList = amt : map (mod amt) cs

   Without currying:
   
makeChange amt cs = zipWith div modList cs
where modList = amt : map doMod cs
doMod x = amt `mod` x