# Calculate the Minimum Number of Coins For Given Amount of Change in Haskell

I am trying to write an algorithm for the Change-making problem.

I am assuming the coin system is canonical, which means the greedy algorithm of always choosing the largest coin that is less than the remaining amount is an optimal algorithm.

`coinChange` is a function to algorithm. The inputs are the amount of money and the denominations for the given coin system. The function outputs the minimum number of coins that are required for each denomination.

For example:

``````Input  : coinChange 34 [1, 5, 10, 25, 50, 100]
Output : [4,1,0,1,0,0]
``````

The type declaration for `coinChange` is:

``````coinChange :: Integer -> [Integer] -> [Integer]
``````

I found this solution and I understand why it works:

``````coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds = (coinChange (c `rem` d) (init ds) ) ++ [c `quot` d]
where d = last ds
``````

However, I got several error messages when I tried to make my own solution.

At first, I tried:

``````coinChange c [] = []
coinChange c ds = reverse ( (c `quot` x): coinChange (c `rem` x) xs )
where (x:xs) = reverse ds
``````

I tried reversing the order of the coin denominations, so I start with the largest first. I thought this would be more convenient than using `last` and `init`.

When I run this I get:

``````coinChange 64 [1,2,5,10,20,50,100]
[64,0,0,0,0,0,0]
``````

It seems strange that I get 64 here.

If I am using a recursive function, I think it is confusing to use `reverse` on the entire list, as parts of the list will be reversed multiple times. So I tried this:

``````coinChange c [] = []
coinChange c ds =reverse( (c `quot` x):(coinChange' (c `rem` x) xs ))
where (x:xs) = (reverse ds)

coinChange' c [] = []
coinChange' c ds = (c`quot`x):(coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds
``````

If I try:

``````coinChange 64 [1,2,5,10,20,50,100]
``````

I thought I would get `[0,2,0,1,0,1,0]` as my final output:

``````(64 `quot` 100):(coinChange' (64 `rem` 100) [1,2,5,10,20,50])
0:((64`quot`50):coinChange' (64`rem`50) [1,2,5,10,20])
0:(1:coinChange' 14 [1,2,5,10,20])
0:(1:((14`quot` 20):coinChange' (14 `rem` 20) [1,2,5,10]))
0:(1:(0:coinChange 14 [1,2,5,10]))
0:(1:(0:((14`quot` 10) : coinChange' (14 `rem` 10) [1,2,5])))
0:(1:(0:( 1 : coinChange' (14 `rem` 10) [1,2,5])))
0:(1:(0:( 1 : coinChange' 4 [1,2,5])))
0:(1:(0:( 1 : ((4 `quot` 5):coinChange' (4`rem` 5) [1,2]))))
0:(1:(0:( 1 : (0:coinChange' 4 [1,2]))))
0:(1:(0:( 1 : (0:((4`quot`2):coinChange (4`rem`2) [1])))))
0:(1:(0:( 1 : (0:(2:coinChange 0 [1])))))
0:(1:(0:( 1 : (0:(2:((0`quot`1):coinChange' (0`rem` 1) []))))))
0:(1:(0:( 1 : (0:(2:(0:coinChange' 0 []))))))
0:(1:(0:( 1 : (0:(2:(0:[]))))))
reverse [0,1,0,1,0,2,0]
final output: [0,2,0,1,0,1,0]
``````

However, when I run this code in the terminal, I get:

``````coinChange 64 [1,2,5,10,20,50,100]
[0,0,0,0,0,64,0]
``````

Why does my approach not work?

I then tried:

``````coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds =  reverse( (c `quot` x): coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds

coinChange' 0 ds = take (length ds) (repeat 0)
coinChange' c ds =  (c `quot` x): coinChange' (c `rem` x) xs
where (x:xs) = reverse ds
``````

I took the line `coinChange 0 ds = take (length ds) (repeat 0)` from the already-working solution.

However, when I run this code in the terminal, I get the same error:

``````coinChange 64 [1,2,5,10,20,50,100]
[0,0,0,0,0,64,0]
``````

I think the main problem is with `where (x:xs) = reverse ds`. Why does this part of the code not work in the way that I expected it to work?

I still get the same error when I use `let` instead of `where`.

coinChange 0 ds = take (length ds) (repeat 0) coinChange c ds = let (x:xs) = reverse ds in reverse( (c `quot` x): coinChange' (c `rem` x) xs )

coinChange' 0 ds = take (length ds) (repeat 0) coinChange' c ds = let (x:xs) = reverse ds in (c `quot` x): coinChange' (c `rem` x) xs

I thought the problem could be that I am using `(x:xs)`.

So, I tried:

``````coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds =  let xs = reverse ds
in reverse( (c `quot` (head xs)): coinChange' (c `rem` (head xs)) (tail xs) )

coinChange' 0 ds = take (length ds) (repeat 0)
coinChange' c ds =  let xs = reverse ds
in (c `quot` (head xs)): coinChange' (c `rem` (head xs)) (tail xs)
``````

This still gave the same error.

I tried to the concatenation operator `(++)`, instead of the prepend operator `:`, to see if that would help:

``````coinChange 0 ds = take (length ds) (repeat 0)
coinChange c ds =  let xs = reverse ds
in coinChange (c `rem` (head xs)) (tail xs) ++ [c `quot` (head xs)]
``````

I still got the same error with this code as well.

It appears that the problem must be with my approach of reversing the list of coin denominations.

Why have all my attempts failed? Why do I keep getting this error with 64, when the quotient should be 1?

Solution

• In this answer I will focus on this attempt of yours:

``````coinChange c [] = []
coinChange c ds =reverse( (c `quot` x):(coinChange' (c `rem` x) xs ))
where (x:xs) = (reverse ds)

coinChange' c [] = []
coinChange' c ds = (c`quot`x):(coinChange' (c `rem` x) xs )
where (x:xs) = reverse ds
``````

I think the problem is indeed in the `where (x:xs) = reverse ds` part in the `coinChange'` function. Each recursive call reverses the list of denominations. So the `xs` you get there from the pattern match in that `where` clause is the reversed list of denominations without the largest denomination. But that list is still reversed, so you shouldn't pass that as an argument to the `coinChange` or `coinChange'` functions again. You can reverse this list again before passing it to the recursive call, but that is not very efficient. I would suggest only reversing the denominations in the `coinChange` function.

Also, the `coinChange` function can be simplified, because it basically only needs to reverse the denominations and the resulting list.

Here is how that would look:

``````coinChange c ds = reverse (coinChange' c (reverse ds))

coinChange' c [] = []
coinChange' c (x:xs) = (c `quot` x) : coinChange' (c `rem` x) xs
``````