Okay, I like Cale's extra guard short circuit so much I must add it to my pseudo-example. Cale's guard:
amount `div` maximum coins > maxCoins = [] -- optimisation
Mine, updated.
partition (x:xs) m k | x>m = partition xs m k -- x is too big
parititon (x:_) m k | x*k < m = [] -- cannot succeed
partition (x:xs) m k | otherwise = let most = min k (div m x) range = [most,most-1..1] use quantity = (\quantity -> prefix (replicate quantity x) (partition xs (m-quantity*x) (k-quantity)) in map use range
The first result from this will be the greediest.
As for memoizing, it would be interesting to attack it differently. Get all the results for a given m and unlimited k and store them sorted by k. Then return the list via takeWhile length up to k. Next call for same m can skip to the takeWhile and be very fast. Pre-generating the table for amounts up to some limit could be done more efficiently with a bottom up approach. -- Chris