Change.hs

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)