change.hs

replaceNth :: (Eq t1, Num t1) => t1 -> t -> [t] -> [t]
replaceNth n b (x:xs)
     | n == 0 = b:xs
     | otherwise = x:replaceNth (n - 1) b xs

giveChange :: (Ord a, Num a, Num t) => a -> [a] -> [t] -> (a, [(Double, t)])
giveChange a c u
  | null c = (a, zip coins u)
  | last c <= a = giveChange (a - last c) c (replaceNth l ((u !! l) + 1) u)
  | otherwise = giveChange a (init c) u
  where l = length c - 1

giveChange' :: (Num t, Num b, Ord b) => b -> [b] -> (b, [(Double, t)])
giveChange' a c = giveChange a c (map (const 0) c)