I had this one all wrong, and made it way more complex than it really was. I'm embarassed to post the final code ... but it is what it is.
Statutory Warning: Spoilers ahead
import Data.Maybe -- Basic idea is something like this: -- [*] given amount and some coins, pick the largest coin -- [*] there are (floor (total/coin)) ways of using this coin value -- [*] but ... NOT ALL of these count! Only the ones that leave a total that can be used with the remaining coins! coins = [1, 2, 5, 10, 20, 50, 100, 200] sortedCoins :: [Int] sortedCoins = L.reverse $ L.sort $ coins combinations :: Int -> [Int] -> Maybe Int combinations total coins = -- T.trace ("total = " ++ show total ++ ", coins = " ++ show coins) $ if total == 0 then Just 1 else case coins of  -> Nothing [c] -> if mod total c == 0 then Just 1 else Nothing c:cs -> if total == 0 then Just 1 else let newTotal total coin num = total - (coin * num) combs = [combinations (newTotal total c num) cs | num <- [0 .. div total c]] counts = sum $ catMaybes combs in if counts == 0 then Nothing else Just counts euler31 :: Int euler31 = fromJust $ combinations 200 sortedCoins
It turns out, I was being overly cautious and could have just used lists in a different way (left in a commented out debug line to show that I needed it).