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).