[Haskell-cafe] Re: Coin changing algorithm

[Yitzchak Gale]

Actually, something along the lines of Dinh's
attempted solution to the original partition
problem is a very nice solution to the coin
changing problem:

Make change for the amount a, using at most
k of the coins cs.
 > coins _  0 _ = [[]]
 > coins _  _ 0 = []
 > coins cs a k = [h:s | t <- init (tails cs),
 >                       let h = head t,
 >                       h <= a,
 >                       s <- coins t (a-h) (k-1)]

(The functions "init" and "tails" are from the
Data.List module.)

Note that Dinh is already using a monad for his
solution, via Haskell's special syntax for the
List monad.

Here it is translated into regular monad syntax:

 > coinsM _  0 k = return []
 > coinsM _  _ 0 = []
 > coinsM cs a k = do
 >   t <- init (tails cs)
 >   let h = head t
 >   unless (h <= a) []
 >   s <- coinsM t (a-h) (k-1)
 >   return (h:s)

(The function "unless" is from the Control.Monad
module.)

-Yitz