неуклюжий стек трансформатора монад

Ваше решение определенно неудобно в использовании (и злоупотреблении) монадами:

• Обычно монады строят по частям, складывая несколько трансформаторов.
• Менее обычно, но все же иногда случается складывать несколько состояний
• Сложить несколько трансформаторов Maybe очень необычно.
• Еще более необычно использовать MaybeT для прерывания цикла

Ваш код слишком бессмысленен:

(`when` mzero) . isJust =<<
   runMaybeT (mapM_ f bases)

вместо того, чтобы легче читать

let isHappy = isJust $ runMaybeT (mapM_ f bases)
when isHappy mzero

Сосредоточившись теперь на функции resolve1, давайте упростим ее. Самый простой способ сделать это - удалить внутреннюю монаду MaybeT. Вместо бесконечного цикла, который прерывается при нахождении счастливого числа, вы можете пойти другим путем и выполнить рекурсию только в том случае, если число не является счастливым.

Более того, вам ведь тоже не нужна монада State? Всегда можно заменить состояние явным аргументом.

Применение этих идей solution1 теперь выглядит намного лучше:

solve1 :: [Integer] -> IsHappyMemo Integer
solve1 bases = go 2 where
  go i = do happyBases <- mapM (\b -> isHappy Set.empty b i) bases
            if and happyBases
              then return i
              else go (i+1)

Я был бы более доволен этим кодом. Остальное ваше решение в порядке. Меня беспокоит то, что вы выбрасываете кеш-память для каждой подзадачи. Есть ли для этого причина?

solve :: [String] -> String
 solve =
    concat .
    (`evalState` Map.empty) .
    mapM f .
   zip [1 :: Integer ..]
  where
    f (idx, prob) = do
      s <- solve1 . map read . words $ prob
      return $ "Case #" ++ show idx ++ ": " ++ show s ++ "\n"

Разве ваше решение не было бы более эффективным, если бы вы вместо этого использовали его повторно?

solve :: [String] -> String
solve cases = (`evalState` Map.empty) $ do
   solutions <- mapM f (zip [1 :: Integer ..] cases)
   return (unlines solutions)
  where
    f (idx, prob) = do
      s <- solve1 . map read . words $ prob
      return $ "Case #" ++ show idx ++ ": " ++ show s

Классы Monad * существуют для устранения необходимости повторного подъема. Если вы измените свои подписи следующим образом:

type IsHappyMemo = Map.Map (Integer, Integer) Bool

isHappy :: MonadState IsHappyMemo m => Set.Set Integer -> Integer -> Integer -> m Bool

Таким образом можно убрать большую часть «лифта». Однако самая длинная последовательность лифтов не может быть удалена, поскольку это монада State внутри StateT, поэтому использование класса типа MonadState даст вам внешний StateT, из которого вам нужно перейти во внутреннее состояние. Вы можете обернуть свою монаду State в новый тип и создать класс MonadHappy, аналогичный существующим классам монад.

ListT (из пакета List) выполняет гораздо более приятную работу, чем MaybeT, останавливая вычисление при необходимости.

solve1 :: [Integer] -> IsHappyMemo Integer
solve1 bases = do
  Cons result _ <- runList . filterL cond $ fromList [2..]
  return result
  where
    cond num = andL . mapL (isHappy Set.empty num) $ fromList bases

Некоторые пояснения того, как это работает:

Если бы мы использовали обычный список, код выглядел бы так:

solve1 bases = do
  result:_ <- filterM cond [2..]
  return result
  where
    cond num = fmap and . mapM (isHappy Set.empty num) bases

Это вычисление происходит в монаде State, но если мы захотим получить результирующее состояние, у нас возникнет проблема, потому что filterM запускает монадический предикат, который он получает для каждого элемента [2..], бесконечного списка.

В монадическом списке filterL cond (fromList [2..]) представляет список, к которому мы можем обращаться к одному элементу за раз как монадическое действие, поэтому наш монадический предикат cond фактически не выполняется (и не влияет на состояние), если мы не потребляем соответствующие элементы списка.

Точно так же реализация cond с использованием andL заставляет нас не вычислять и обновлять состояние, если мы уже получили False результат одного из isHappy Set.empty num вычислений.