Folding Up the Coin Changer Kata

"Whate'er the course, the end is the renown."
-- Shakespeare, All's Well That Ends Well
Act IV Scene IV, Line 36

Coin Changer Kata

The Coin Changer kata has three things which make it a good kata.

1. easy to understand
2. rich set of features
3. lots of realistic possible implementations

Even in today's cashless society, most people understand the idea of handing someone over some money and get change back.  This handing back of change requires the breaking down of the change over coins of different denominations.  Finding which coins to hand back has lots of possible implementations which translate over to things which programmers do every day.

The user story is very simple:

Given a collection of coins of different denominational value
When an amount of change is given
Then it will give back the number of coins for each denomination needed using the least amount of coins possible

A type signature for the function needed could look like the following:

changeFor(coins: int[], amount: int): int[]

We are expecting an array of integers which have different denomination of coins (in the US something like: [25, 10, 5, 1]) and the amount of change needed (something like: 99) giving a resulting array of integers showing how many of each denomination (something like: [3, 2, 0, 4]).

What would we need to be able to do this kata using just Fold?

We'll need to use a tuple (or something like one) to manage the state of the amount of change needed and the resulting array of integers.

Now lets look at an example using a typical full US register with quarters, dimes, nickels, and pennies.  We'll look at getting change for 99 cents.

First Memorize has (99, empty) and X has 25 giving the result of (24, [3]).

Next Memorize has (24, [3]) and X has 10 giving the result of (4, [3, 2]).

Then Memorize has (4, [3, 2]) and X has 5 giving the result of (4, [3, 2, 0]).

Last Memorize has (4, [3, 2, 0]) and X has 1 giving the result of (0, [3, 2, 0, 4]).

Finally obtaining the tuple item with the resulting array of integers to get the change.

Clojure

We see with the Clojure code that we seed with a map with a key for the :amount and one for the :result.  We fold over the coins using reduce destructing the memoize value into the amount and result.  We then just calculate the new amount using: amount % coin, follow by inserting the number of coins we get using: amount / coin.  We use cons to show off the coolness that is the thread-last macro (at least that is why I think I coded it this way, it was a little bit ago that I did the gist and I cannot remember why I code with cons over conj).

C#

We see with the C# code that we seed using a Tuple (which I think has very ugly syntax in C#).  We then fold over the coins using aggregate just like the Clojure code above.  We calculate the changer results and place them into a new Tuple which we return as the memoize.

ECMAScript 2015

In this ECAMScript 2015 example we use lodash's foldl to fold over the coins just like the two examples above.  The seed value is a simple JavaScript object with the members of amount and result given.  We are a bit dirty and mutate the memoize on each call with the changer results but we could argue that this is still "pure" since the mutation happens to an item which is created and used only in side the function.

ECMAScript 2015 and Immutable.js

Last we look at Facebook's open source Immutable.js.  We create an immutable List with the coins which we use to fold over the values using reduce.  The seed value we give it is a simple JavaScript array with an immutable List to hold the results and the amount passed in.  We could use an immutable Map if we wanted to keep it purely immutable.  Like this:



I am not a huge fan of stringly typed accessors, but I understand why they use them.  Both ways are good and would really come down to to performance and readability.

The End

Thus ends our tour of All You Need is Fold, but this is not the end of the uses of Fold, for Fold is universal.