# 07.26.07

## Exercise 5.9

Posted in Uncategorized at 11:20 pm by admin

```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```

See technical error 12 for a note about this exercise.

## 2 Comments »

1. Julian said,

April 11, 2010 at 4:48 am

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 in head bests```
2. Ricky Liu said,

February 19, 2014 at 5:42 am

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 ```