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.
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)
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)
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)
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)
Oh yeah, it does return a list of Ints. My mistake.
Yes, the underscore means “match anything”.
(http://livejournal.com/users/elbeno)
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)
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)