coins.hs

import Data.List

data Coin = Coin Integer String

instance Show Coin where
    show (Coin _ name) = name

currency =
    [ Coin 25 "quarter"
    , Coin 10 "dime"
    , Coin  5 "nickel"
    , Coin  1 "penny"
    ]

opt1 n = (remainder, reverse change) where
    (remainder, change)              = opt (n, []) currency
    opt (n, coins) []                = (n, coins)
    opt (n, coins) (c@(Coin v _):cs) = case divMod n v of
                                           (0, _) -> opt (n, coins) cs
                                           (a, b) -> opt (b, (a, c) : coins) cs

opt2 n = (remainder, reverse change) where
    (remainder, change)         = foldl' opt (n, []) currency
    opt (n, coins) c@(Coin v _) = case divMod n v of
                                      (0, _) -> (n, coins)
                                      (a, b) -> (b, (a, c) : coins)

optimal = opt2

main = do
    let f (n, c) = "\t" ++ show n ++ "\t" ++ show c

    let change     = 57
    let (n, coins) = optimal change
    let lines      = map f coins

    putStrLn ("The optimal change for " ++ show change ++ " is:\n")
    putStrLn (intercalate "\n" lines)
    putStrLn ("\n...with " ++ show n ++ " cents left over")