Coin change problem

change.hs

import Control.Applicative
import Data.Maybe
import Data.Array
import Data.List

-- UK coin values in pence
coins :: [Int]
coins = [500, 200, 100, 50, 20, 10, 5, 2, 1]

-- Helper functions
sub :: (Num a, Ord a) => a -> a -> Maybe a
sub x y
  | result < 0 = Nothing
  | otherwise  = Just result 
  where
    result = x - y

minimum' :: Ord a => [Maybe a] -> Maybe a
minimum' xs = case catMaybes xs of                                              
                []  -> Nothing                                                  
                xs' -> Just (minimum xs')

-- Recursive solution
change :: [Int] -> Int -> Maybe Int
change coins amount
  | amount `elem` coins = Just 1
  | otherwise           = succ <$> (minimum' $ map change' coins)
  where 
    change' coin = sub amount coin >>= change coins

-- Dynamic programming
dchange :: [Int] -> Int -> Maybe Int
dchange coins initial = go initial
  where
    go :: Int -> Maybe Int
    go 0 = Just 0
    go amount
      | amount `elem` coins = Just 1
      | otherwise = succ <$> (minimum' $ map (dchange' amount) coins)
    dchange' x coin = sub x coin >>= (!) table
    table = listArray (0, initial) $ map go [0..initial]

-- Greedy algorithm - can give incorrect solutions
gchange :: [Int] -> Int -> Maybe Int
gchange
  = gchange' . reverse . sort
  where
    gchange' [] _ = Nothing
    gchange' _ 0  = Just 0
    gchange' (c : cs) amount
      | amount >= c = succ <$> gchange' (c : cs) (amount - c)
      | otherwise   = gchange' cs amount