Монадный трансформатор стекается с MaybeT и RandT

Question

Я пытаюсь узнать, как работают Monad Transformers, переформулировав то, что я написал, когда впервые изучил Haskell. В нем довольно много компонентов, которые могут быть заменены (довольно большим) стеком монадных трансформаторов.

Я начал с написания псевдонима типа для моего стека:

type SolverT a = MaybeT
                    (WriterT Leaderboard
                        (ReaderT Problem
                            (StateT SolutionState
                                (Rand StdGen)))) a

Краткое краткое изложение:

• Rand пронизывает StdGen используется в различных случайных операциях
• StateT несет состояние решения, поскольку оно постепенно оценивается
• ReaderT имеет фиксированное состояние
• WriterT список лидеров постоянно обновляется решением с лучшими версиями
• MaybeT необходимо, потому что и проблема, и состояние решения используют lookup от Data.Mapи любая ошибка в том, как они настроены, приведет к Nothing

В оригинальной версии Nothing "никогда" не произошло, потому что я использовал только Map для эффективного поиска для известных пар ключ / значение (я полагаю, я мог бы реорганизовать использование массива). В оригинале я обошел Maybe проблема путем либерального использования fromJust,

Из того, что я понимаю, имея MaybeT вверху означает, что в случае Nothing в любой SolverT a Я не теряю никакой информации в других моих преобразователях, поскольку они развернуты извне.

Дополнительный вопрос

[РЕДАКТИРОВАТЬ: Это была проблема, потому что я не использовал песочницу, поэтому у меня были старые / конфликтующие версии библиотек, вызывающие проблему]

Когда я впервые написал стек, у меня было RandT на вершине. Я решил избежать использования lift везде или писать свои собственные объявления экземпляров для всех других трансформаторов для RandT, Поэтому я переместил его на дно.

Я попытался написать объявление экземпляра для MonadReader и это было примерно столько, сколько я мог получить для компиляции:

instance (MonadReader r m,RandomGen g) => MonadReader r (RandT g m) where
    ask = undefined
    local = undefined
    reader = undefined

Я просто не мог получить какую-либо комбинацию lift, liftRand а также liftRandT работать в определении. Это не особенно важно, но мне интересно, какое может быть правильное определение?

Проблема 1

[РЕДАКТИРОВАТЬ: Это была проблема, потому что я не использовал песочницу, поэтому у меня были старые / конфликтующие версии библиотек, вызывающие проблему]

Несмотря на то, что в MonadRandom есть экземпляры всего (кроме MaybeT), мне все равно приходилось писать собственные объявления экземпляров для каждого Transformer:

instance (MonadRandom m) => MonadRandom (MaybeT m) where
    getRandom = lift getRandom
    getRandomR = lift . getRandomR
    getRandoms = lift getRandoms
    getRandomRs = lift . getRandomRs

Я сделал это для WriterT, ReaderT а также StateT копируя экземпляры из исходного кода MonadRandom. Примечание: для StateT а также WriterT они используют квалифицированный импорт, но не для Reader. Если я не писал свои собственные объявления, я получал такие ошибки:

No instance for (MonadRandom (ReaderT Problem (StateT SolutionState (Rand StdGen))))
  arising from a use of `getRandomR'

Я не совсем уверен, почему это происходит.

Проблема 2

Учитывая вышесказанное, я переписал одну из своих функций:

randomCity :: SolverT City
randomCity = do
    cits <- asks getCities
    x <- getRandomR (0,M.size cits -1)
    --rc <- M.lookup x cits
    return undefined --rc

Вышеуказанные компиляции, и я думаю, как предполагается использовать трансформаторы. Несмотря на утомительную необходимость писать повторяющиеся экземпляры трансформатора, это довольно удобно. Вы заметите, что выше я закомментировал две части. Если я удалю комментарии, я получу:

Couldn't match type `Maybe'
              with `MaybeT
                      (WriterT
                         Leaderboard
                         (ReaderT Problem (StateT SolutionState (Rand StdGen))))'
Expected type: MaybeT
                 (WriterT
                    Leaderboard (ReaderT Problem (StateT SolutionState (Rand StdGen))))
                 City
  Actual type: Maybe City

Сначала я думал, что проблема была в типах монад, которые они есть. Все остальные монады в стеке имеют конструктор для (\s -> (a,s)) в то время как, возможно, имеет Just a | Nothing, Но это не должно иметь значения, тип для ask должен вернуться Reader r a, в то время как lookup k m должен дать тип Maybe a,

Я думал, что проверю свое предположение, поэтому я пошел в GHCI и проверил эти типы:

> :t ask
ask :: MonadReader r m => m r
> :t (Just 5)
(Just 5) :: Num a => Maybe a
> :t MaybeT 5
MaybeT 5 :: Num (m (Maybe a)) => MaybeT m a

Я вижу, что все мои другие преобразователи определяют класс типа, который можно поднять через преобразователь. MaybeT кажется, не имеет MonadMaybe класс типов.

Я знаю что с lift Я могу поднять что-то из моего стека трансформатора в MaybeTтак что я могу в конечном итоге MaybeT m a, Но если я в конечном итоге Maybe a Я предполагал, что смогу связать это в do блокировать с <-,

Проблема 3

У меня на самом деле есть еще одна вещь, чтобы добавить в свой стек, и я не уверен, куда он должен идти. Solver работает на фиксированном количестве циклов. Мне нужно отслеживать текущий цикл против максимального цикла. Я мог бы добавить счетчик циклов к состоянию решения, но мне интересно, есть ли дополнительный трансформатор, который я мог бы добавить.

В дополнение к этому, сколько трансформаторов слишком много? Я знаю, что это невероятно субъективно, но наверняка есть затраты производительности на этих трансформаторах? Я предполагаю, что некоторое количество слияния может оптимизировать это во время компиляции, так что, может быть, затраты на производительность минимальны?

Answer 1

Проблема 1

Не могу воспроизвести. Уже есть эти случаи для RandT,

Проблема 2

lookup возвращается Maybe, но у вас есть стек, основанный на MaybeT, Причина, почему нет MonadMaybe является то, что соответствующий класс типа MonadPlus (или более общий Alternative) - pure/return соответствовать Just а также empty/mzero соответствовать Nothing, Я бы предложил создать помощника

lookupA :: (Alternative f, Ord k) => k -> M.Map k v -> f v
lookupA k = maybe empty pure . M.lookup k

и тогда вы можете позвонить lookupA где вам нужно в вашем стеке монад

Как уже упоминалось в комментариях, я настоятельно рекомендую использовать RWST, поскольку это именно то, что подходит для вашего случая, и с ним гораздо проще работать, чем со стеком StateT/ReaderT/WriterT.

Также подумайте о разнице между

type Solver a = RWST Problem Leaderboard SolutionState (MaybeT (Rand StdGen)) a

а также

type Solver a = MaybeT (RWST Problem Leaderboard SolutionState (Rand StdGen)) a

Разница в том, что происходит в случае сбоя. Первый стек ничего не возвращает, а второй позволяет получить состояние и Leaderboard вычислил до сих пор.

Проблема 3

Самый простой способ - добавить его в государственную часть. Я просто включил бы это в SolutionState,

Образец кода

import Control.Applicative
import Control.Monad.Random
import Control.Monad.Random.Class
import Control.Monad.Trans
import Control.Monad.Trans.Maybe
import Control.Monad.RWS
import qualified Data.Map as M
import Data.Monoid
import System.Random

-- Dummy data types to satisfy the compiler
data Problem = Problem
data Leaderboard = Leaderboard
data SolutionState = SolutionState
data City = City

instance Monoid Leaderboard where
  mempty = Leaderboard
  mappend _ _ = Leaderboard

-- dummy function
getCities :: Problem -> M.Map Int City
getCities _ = M.singleton 0 City

-- the actual sample code

type Solver a = RWST Problem Leaderboard SolutionState (MaybeT (Rand StdGen)) a

lookupA :: (Alternative f, Ord k) => k -> M.Map k v -> f v
lookupA k = maybe empty pure . M.lookup k

randomCity :: Solver City
randomCity = do
    cits <- asks getCities
    x <- getRandomR (0, M.size cits - 1)
    lookupA x cits