Change in Haskell using State monad

Change.hs

module Change (findFewestCoins) where

import Control.Monad.State
import Data.Function (on)
import Data.Map (Map, (!?))
import qualified Data.Map as Map
import Safe.Foldable (minimumByMay)

findFewestCoins :: Integer -> [Integer] -> Maybe [Integer]
findFewestCoins target coins = evalState (memoFind coins target) Map.empty

memoFind :: [Integer] -> Integer -> State (Map Integer (Maybe [Integer])) (Maybe [Integer])
memoFind coins target =
  case compare target 0 of
    LT -> return Nothing
    EQ -> return $ Just []
    GT -> do
      cache <- get
      case cache !? target of
        Just x -> return x
        Nothing -> do
          solns <- mapM (memoFind coins) $ map (target -) coins
          let candidates = [coin : solution | (coin, Just solution) <- zip coins solns]
          let best = minimumByMay (compare `on` length) $ candidates
          modify $ Map.insert target best
          return best