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 Responses to “Haskell problem”

  1. greatbiggary says:

    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. elbeno says:

    I was evidently tired last night. I didn't spot that
    newamt = amt - n * v
    is more readably:
    newamt = amt `mod` v

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

  3. elbeno says:

    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)

  4. greatbiggary says:

    Actually, in your post you wrote:

    makeChange :: Int -> [Int] -> [Int]

    I thought it was to return a list of ints. I do like the syntax with the underscore, though. Does that character always mean “doesn't matter?”

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

  5. elbeno says:

    Oh yeah, it does return a list of Ints. My mistake.
    Yes, the underscore means “match anything”.

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

  6. elbeno says:

    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)

  7. elbeno says:

    Hmmm… well in fact, it occurs to me that any other variable name would also match anything. The underscore is just a way of saying “I don't care to name this parameter” to make the code clearer.

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

Leave a Reply