Using Haskell map when functions needs an intermediate result

Question

I'm working thorough a Haskell text and have come across a question about making change. I'm given an ordered list of (denomonation, numCoins) tuples along with an amount and need to return a list of how many of each coin was used to make change. I have the following code that solves the problem:

useCoins :: (Int,Int) -> Int -> Int
useCoins (denomination, numCoins) target = min numCoins (target `div` denomination)

makeChange :: [(Int, Int)] -> Int -> [Int]
makeChange [] target = []
makeChange ((denomination, numCoins):xs) target = 
  let
     coinsUsed = useCoins (denomination, numCoins) target
  in coinsUsed : makeChange xs (target - (coinsUsed * denomination))

The problem is that this is in a chapter on higher-order functions and I'm having a hard time coming up with a way to use map as the target value is changing as it drops through the list. I'd love any help.

Thanks.

-mh

Answer 1

map is the wrong function to use, because as you note it only works for situations where each element can be handled independently, not when elements depend on each other.

However, makeChange is a function that is implementable with a fold. Specifically, your implementation incorporates all the feature of a left fold, but done by hand; you can instead implement your function in terms of foldl'.