Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
module Change where
data Coin a = Penny a | Nickel a | Dime a | Quarter a deriving (Eq, Ord, Show)
type Coins = [Coin Int]
denominations = [1, 5, 10, 25]
coinCount :: Int -> Int -> Coin Int
coinCount amount denomination
| denomination == 1 = Penny (amount `div` denomination)
| denomination == 5 = Nickel (amount `div` denomination)
| denomination == 10 = Dime (amount `div` denomination)
| denomination == 25 = Quarter (amount `div` denomination)
| otherwise = undefined
present :: (Ord a, Num a) => Coin a -> Bool
present (Penny n) = n > 0
present (Nickel n) = n > 0
present (Dime n) = n > 0
present (Quarter n) = n > 0
maxCoinCounts :: Int -> Coins
maxCoinCounts amount = filter present (map (coinCount amount) denominations)
makePartialChange :: Int -> Coin Int
makePartialChange = maximum . maxCoinCounts
coinCountValue :: Coin Int -> Int
coinCountValue (Penny n) = n
coinCountValue (Nickel n) = n * 5
coinCountValue (Dime n) = n * 10
coinCountValue (Quarter n) = n * 25
amountRemaining :: Int -> Coin Int -> Int
amountRemaining n coin
| coinCountValue coin <= n = n - coinCountValue coin
| otherwise = n
makeExactChange :: Int -> Coins
makeExactChange amount = changemaker amount [] (makePartialChange amount)
where
changemaker 0 change coin = change
changemaker n change coin = changemaker (amountRemaining n coin) (change ++ [coin]) (makePartialChange $ amountRemaining n coin)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment