# Exercise 5.9

```makeChange :: Int -> [Int] -> [Int]
makeChange _ [] = []
makeChange 0 _ = []
makeChange amt (v:vs) = n : (makeChange newamt vs)
where n = amt `div` v
newamt = amt `mod` v```

This was one tricky to do with higher-order functions, until I discovered scanl.

```makeChange' :: Int -> [Int] -> [Int]
makeChange' amt vs = zipWith div modvs vs
where modvs = scanl mod amt vs```

### 2 responses to “Exercise 5.9”

1. Julian says:

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 ++  ++ 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
2. Ricky Liu says:
``` makeChange amt cs = zipWith div modList cs where modList = amt : map (mod amt) cs ```
``` makeChange amt cs = zipWith div modList cs where modList = amt : map doMod cs doMod x = amt `mod` x ```