StateT и недетерминистская монада: простой пример

Question

В рамках обучения работе с StateT и недетерминированным монадой я хотел бы написать функцию, которая использует их для перечисления разделов целого числа (при этом разрешается многократное использование целых чисел). Например, передав аргумент 4 должно привести к [[1,1,1,1],[1,1,2],[2,2],[1,3],[4]] (уникальность не имеет значения, меня больше интересует только получение рабочего кода).

(Кроме того, я знаю, что существует рекурсивное решение для генерации разделов, а также динамическое программирование и создание решений на основе функций для подсчета разделов - цель этого упражнения - создать минимальный рабочий пример, сочетающий в себе StateT и [].)

Вот моя попытка, которая была разработана для работы с любым вводом, меньшим или равным 5:

{-# LANGUAGE NoImplicitPrelude #-}
{-# OPTIONS_GHC -Wall #-}

import CorePrelude
import Control.Monad.State.Lazy

sumState :: StateT Int [] [Int]
sumState = do
  m <- lift [1..5]
  n <- get <* modify (-m+)
  case compare n 0 of
    LT -> mzero
    EQ -> return [m]
    GT -> fmap (n:) sumState

runner :: Int -> [([Int],Int)]
runner = runStateT sumState

я использую runStateT скорее, чем evalStateT чтобы помочь с отладкой (полезно видеть значения конечного состояния). Как я уже сказал, я не слишком беспокоюсь о создании уникальных разделов, так как сначала хотел бы просто понять, как правильно использовать эти две монады вместе.

Загрузка в GHCi и оценивая runner 4 приводит к следующему, и я запутался, почему приведенный выше код производит этот вывод.

[([4,3,2,1,1],-1),([4,3,2,1,2],-2),([4,3,2,1,3],-3),([4,3,2,1,4],-4),([4,3,2,1,5],-5),([4,3,2,1],-1),([4,3,2,2],-2),([4,3,2,3],-3),([4,3,2,4],-4),([4,3,2,5],-5),([4,3,1,1],-1),([4,3,1,2],-2),([4,3,1,3],-3),([4,3,1,4],-4),([4,3,1,5],-5),([4,3,1],-1),([4,3,2],-2),([4,3,3],-3),([4,3,4],-4),([4,3,5],-5),([4,2,1,1],-1),([4,2,1,2],-2),([4,2,1,3],-3),([4,2,1,4],-4),([4,2,1,5],-5),([4,2,1],-1),([4,2,2],-2),([4,2,3],-3),([4,2,4],-4),([4,2,5],-5),([4,1,1],-1),([4,1,2],-2),([4,1,3],-3),([4,1,4],-4),([4,1,5],-5),([4,1],-1),([4,2],-2),([4,3],-3),([4,4],-4),([4,5],-5)]

Что я делаю неправильно? Как правильно комбинировать StateT и [] для перечисления разделов?

Answer 1

У тебя просто две маленькие ошибки. Первый здесь:

n <- get <* modify (-m+)

Это получает значение n прежде чем вычесть m, Вы почти наверняка хотите

n <- modify (-m+) >> get

вместо или

modify (-m+)
n <- get

если вы предпочитаете это правописание. Другое - вы помещаете текущее состояние в список вместо значения, которое вы добавляете в GT ветка:

GT -> fmap (n:) sumState

Изменить это на

GT -> fmap (m:) sumState

а ты золотой

*Main> runner 4
[([1,1,1,1],0),([1,1,2],0),([1,2,1],0),([1,3],0),([2,1,1],0),([2,2],0),([3,1],0),([4],0)]