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 _______________________________________________ Haskell-Cafe mailing list [email protected] http://www.haskell.org/mailman/listinfo/haskell-cafe
