[Haskell-cafe] Coin changing algorithm

[Cale Gibbard]

heh, just noticed that the (amount > 0) test in the last guard is
unnecessary (other cases added since then leave only that as a
possibility) and it can be replaced by "otherwise", not that it makes
too much of a difference:

> import Monad
> import List
> 
> makeChange :: [Integer] -> Integer -> Integer -> [[Integer]]
> makeChange coins amount maxCoins
>     | amount < 0  = []
>     | amount == 0 = [[]]
>     | null coins  = []
>     | amount `div` maximum coins > maxCoins = [] -- optimisation
>     | otherwise =
>         do x <- coins
>            xs <- makeChange (filter (<= x) coins)
>                             (amount - x)
>                             (maxCoins - 1)
>            guard (genericLength (x:xs) <= maxCoins)
>            return (x:xs)
> 
> makeChange' :: Integer -> Integer -> [[Integer]]
> makeChange' amount maxCoins = makeChange coins amount maxCoins
>     where coins = [200,100,50,20,10,5,2,1]
> 
 -- Cale