Now, how to put this algorithm into Haskell? Something like
seems like the form we will want. Let's consider how this repetition of next_coins will end and whether the choice of having the state be the coins rather than the amount was correct.
Within the next_coin function, we must make use of both the amount and the coins. There it doesn't seem to matter which is the interior object and which is the state. The interior object is available as a parameter and the state is available through get and put.
Outside of next_coin, it is a different story. There all we need to work with is the amount. We need it to know when to stop the repetition of next_coin. There is no need to know anything about the coins when implementing our imagined sequence of next_coins above. By making the amount left to distribute be next_coin's interior object, we can plan a function responsible for repeating next_coins which will have access to the amount left to distribute through >>=.
Remark:
If you do fuzzy reasoning like this and get it wrong. You can always back up and try again.
Now we can nail down some of the type definitions: Since dispense requires the IO monad, we will define our state machine type using IO as the wrapper monad in StateT. The definition is
Remark:
Why not StateT Coins IO Int? For the same reason show_result was defined with a rather than [Char], namely the interior object will need to be () at some point.
Continuing with our type defintions: substituting in the StateT definition we see that the runStateT function is
Moreover we now have types for next_coin and dispense