The `change` function appears not to always give the right answer

[JeffreyBenjaminBrown]

When I run the change function from the section on futumorphisms, it reports that there are 3 ways to make change for 10 cents. But it seems like there are four: a dime, two nickels, a nickel and five cents, or ten cents.

That's the only error I see below 15. For numbers greater than 14 I suspect it might always be wrong:

> mapM_ (putStrLn . show) $ map (id &&& change) [0..16]
(0,1)
(1,1)
(2,1)
(3,1)
(4,1)
(5,2)
(6,2)
(7,2)
(8,2)
(9,2)
(10,3)
(11,4)
(12,4)
(13,4)
(14,4)
(15,4)
(16,4)

[JeffreyBenjaminBrown]

Also no matter what input I provide, I can't seem to get a returned value greater than 16.

[twitu]

I'm facing the same issue. I can't figure out where change is going wrong.

There's also a small ambiguity in the problem it is solving. The blog links to the change making problem wiki page. This page says that problem tries to find the minimum number of coins required to change a value, while the blog is trying to count all the ways in which the value can be changed.

In either case change does not appear to give the correct answer. For e.g. change 10 returns 3 but the answer is different for different problems -

• minimum number of coins for 10 is 1 because you can change it using { 10 }
• number of ways to change 10 is 4 because you can change it like - { 1, 1, ... 10 times }, { 1, 1, 1, 1, 1, 5 }, { 5, 5 }, {10}
• number of ordered ways to change 10 is 9 because there are 5 more ways to arrange { 1, 1, 1, 1, 1, 5 }.

It'll be great if the author could help with issuing a correction or fix.

[twitu]

I took a look at #1 which gives solution to ordered change counting. And then also at some unordered change counting implementations.

As far as I can understand unordered change counting is not possible to implement with histomorphisms since it requires a specific "ordering" in which various sub problems should be visited, which is not a property of histomorphisms.