Change in Haskell using explicit memoization instead of State monad

Change.hs

module Change (findFewestCoins) where

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

type Change = Maybe [Integer]
type Cache = Map Integer Change

findFewestCoins :: Integer -> [Integer] -> Change
findFewestCoins target coins = snd $ findAndUpdateCache Map.empty target where
  findAndUpdateCache :: Cache -> Integer -> (Cache, Change)
  findAndUpdateCache cache target' =
    case compare target' 0 of
      LT -> (cache, Nothing)
      EQ -> (cache, Just [])
      GT -> case cache !? target' of
        Just solution -> (cache, solution)
        Nothing -> (Map.insert target' solution cache', solution) where
          (cache', solutions') = foldl (solveAndUpdate target') (cache, []) coins
          candidates = [coin : solution' | (coin, Just solution') <- solutions']
          solution = minimumByMay (compare `on` length) candidates

  solveAndUpdate :: Integer -> (Cache, [(Integer, Change)]) -> Integer -> (Cache, [(Integer, Change)])
  solveAndUpdate target (cache, ys) coin = (cache', (coin, solution) : ys)
    where (cache', solution) = findAndUpdateCache cache $ target - coin