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