CoinChange.hs

coinSet = [1, 2, 5, 10, 20, 50, 100, 150, 200, 300]

-- When no coins are available, there is one way to get 0, no ways to get any other number
coins0 = 1:repeat 0

-- Given the result for previous coins, produce a list of possibilities for this coin type
coinsN coin preCoins = go 
  where 
    -- We can either get the value by using other coins or from an earlier value in this list
    -- Skip the first `coin` values
    go = zipWith (+) preCoins $ replicate coin 0 ++ go

-- To find the number of ways to get a value, we index into the list
-- but make the list strict on values first, so we don't build up thunks
getCoinN coinSet n = strictList allCoins !! n
 where 
   -- We chain together the coin specific functions with a fold
   -- ending with no coins available, where we can only produce the number 0.
   allCoins = foldr coinsN coins0 coinSet

main = print $ getCoinN coinSet 300

-- Make a list strict on values, so we don't build up thunks
strictList (x:xs) = x `seq` (x: strictList xs)
strictList [] = []