Haskell problem

Define a function makeChange that, given a nonnegative integer amount and a list of coin denominations, returns a list of the number of coins of each denomination required to make up the amount. For example:

makeChange 99 [5,1] => [19,4]

i.e. 19 nickels and 4 pennies equals 99 cents. To make life easier, you may assume that the list of denominations is in descending order, and that the penny is always included.

I have the following, which works:

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

However, the problem is at the end of a chapter about using higher order functions like map, foldl, foldr, zip, etc. I have a feeling there’s a way to do this problem that way too. But it’s late and Mrs Elbeno is calling me to bed. AOAP.

7 comments

  1. For a moment there, I thought you were writing something to solve the Knapsack Problem. I thought “OMG, he's insan… oh, I see.”

    Haskell reads to me as Perl reads to most everyone else. I.e. as Greek*.

    * excluding, of course, Greeks**
    ** whether or not they know Perl

    (http://livejournal.com/users/greatbiggary)

  2. I find Haskell easy to read.
    makeChange :: Int -> [Int] -> Int
    This is the type signature. It says that makeChange is a function that takes an Int and a list of Ints, and returns an Int. So why doesn't it say:
    makeChange :: Int, [Int] -> Int
    I hear you thinking. And I think the answer is because of currying. i.e. partial function application. That is, you could call makeChange with only one argument (an Int) and the type of the result would be a function that takes a list of Ints and returns an Int.
    The rest of the function definition is just equations, really. With some pattern matching on the formal arguments. i.e.
    makeChange _ [] = []
    means: if the second argument is the empty list (we don't care what the first argument is), return the empty list.
    makeChange amt (v:vs) = ...
    means: otherwise, my first argument will be called amt and I'll call the head of the second argument (the list) v, and its tail I'll call vs.

    (http://livejournal.com/users/elbeno)

  3. Btw, in Haskell, it's optional to include the type signature in the source. Haskell can (usually?) deduce a correct type for a function. But actually, I find that writing the type signature first makes the function easier to write and reason about, and it means I have everything straight in my head.

    (http://livejournal.com/users/elbeno)

Leave a comment

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.