haskellrecursionmodular-arithmeticcoin-change# 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
```

- Comparing lists in Haskell
- Is there a non-identity monad morphism M ~> M that is monadically natural in M?
- Problem with loading module ‘Distribution.Simple’
- Improving efficiency in Stirling numbers calculation
- Does sequencing an infinite list of IO actions by definition result in a never-ending action? Or is there a way to bail out?
- How to call pgQuery from postgresql-query?
- How to avoid whitespace after a tag (link) in Hamlet templates?
- Understanding type-directed resolution in Haskell with existential types
- Why is seq bad?
- Understanding bind function in Haskell
- How to create route that will trigger on any path in Servant?
- How do I use a global state in WAI middleware?
- nixos 23.11 cabal install mysql-simple problem - "Missing (or bad) C libraries"
- Is there a way to kill all forked threads in a GHCi session without restarting it?
- Why can an invalid list expression such as 2:1 be assigned to a variable, but not printed?
- Iterate over a type level list and call a function based on each type in the list
- How does this solution of Project Euler Problem 27 in the Haskell Wiki work?
- Why `Monad` is required to use `pure`?
- Can't do partial function definitions in GHCi
- recommended way to convert Double -> Float in Haskell
- Haskell profiling understanding cost centre summary for anonymous lambda
- Why is Haskell fully declarative?
- GHC Generating Redundant Core Operations
- Question about Event firing in reflex-frp
- Using Haskell's "Maybe", type declarations
- How can I elegantly invert a Map's keys and values?
- Why there is no output for wrapped IO in Haskell?
- What are the definitions of Weather and Memory in xmobar repo?
- Serializing a Data.Text value to a ByteString without unnecessary \NUL bytes
- Using Haskell with VS Code