В чем разница между разными порядками одних и тех же монадных трансформаторов?

Я пытаюсь определить API для выражения определенного типа процедуры в моей программе.

newtype Procedure a = { runProcedure :: ? }

Существует состояние, состоящее из сопоставления идентификаторов с записями:

type ID = Int
data Record = { ... }
type ProcedureState = Map ID Record

Существует три основных операции:

-- Declare the current procedure invalid and bail (similar to some definitions of fail for class Monad)
abort :: Procedure ()
-- Get a record from the shared state; abort if the record does not exist.
retrieve :: ID -> Procedure Record
-- Store (or overwrite) a record in the shared state.
store :: ID -> Record -> Procedure ()

У меня есть несколько целей с этими операциями:

Процедуры могут делать предположения (в отличие от вызова raw Map.lookup) о какие записи доступны, и если любые их предположения ошибочны, Процедура в целом возвращается отказ.
Ряд процедур может соединяться цепью, используя <|> (от класс Альтернатива), чтобы упасть вернуться к процедурам, которые различные предположения. (Похожий на STM orElse)

Учитывая эти цели, я считаю, что мне нужна комбинация монадов State и Maybe.

-- Which to choose?
type Procedure a = StateT ProcedureState Maybe a
type Procedure a = MaybeT (State ProcedureState) a

Я не могу понять, как будут вести себя два порядка Maybe и State. Может ли кто-нибудь объяснить разницу в поведении между двумя порядками?

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

Вывод: Все три ответа были полезны, но была одна общая идея, которая помогла мне решить, какой заказ я хотел. Посмотрев на тип возврата runMaybeT/runStateT, было легко увидеть, какая комбинация имела поведение, которое я искал. (В моем случае мне нужен тип возврата Maybe (ProcedureState, a)).

Ответ 1

Изменить: я изначально получил случаи назад. Исправлено.

Разница между порядками стеков трансформаторов монады действительно имеет значение только тогда, когда вы снимаете слои стека.

type Procedure a = MaybeT (State ProcedureState) a

В этом случае вы сначала запускаете MaybeT, в результате чего вычисляется состояние, которое возвращает Maybe a.

type Procedure a = StateT ProcedureState Maybe a

Здесь StateT - внешняя монада, а это означает, что после запуска StateT с начальным состоянием вам будет присвоен Maybe (a, ProcedureState). То есть вычисление может быть выполнено или может не иметь.

Итак, вы выбираете, зависит от того, как вы хотите обрабатывать частичные вычисления. С MaybeT снаружи вы всегда получите какое-то возвращаемое состояние независимо от успеха вычисления, которое может быть полезным или не может быть полезным. С StateT снаружи вы гарантируете, что все транзакции с сохранением состояния действительны. Из того, что вы описали, я, вероятно, использовал бы сам вариант StateT, но я ожидаю, что он сможет работать.

Единственное правило для упорядочения монада-трансформатора заключается в том, что если используется IO (или другая не-трансформаторная монада), это должно быть дно стека. Обычно люди будут использовать ErrorT в качестве следующего нижнего уровня, если это необходимо.

Ответ 2

В дополнение к другим ответам я хотел бы описать, как это понять в общем случае. То есть, учитывая два трансформатора, какова семантика их двух комбинаций?

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

Шаг 1: создайте таблицу основных типов монадов и их соответствующих типов трансформаторов:

transformer           type                  base type (+ parameter order)

---------------------------------------------------------------

MaybeT   m a        m (Maybe a)            b.    Maybe b

StateT s m a        s -> m (a, s)          t b.  t -> (b, t)

ListT    m a        m [a]                  b.    [] b

ErrorT e m a        m (Either e a)         f b.  Either f b

... etc. ...

Шаг 2: применяйте каждый монадный трансформатор к каждой из базовых монад, подставляя для параметра типа m:

inner         outer         combined type

Maybe         MaybeT        Maybe (Maybe a)
Maybe         StateT        s -> Maybe (a, s)      --  <==  this !!
... etc. ...

State         MaybeT        t -> (Maybe a, t)      --  <== and this !!
State         StateT        s -> t -> ((a, s), t)
... etc. ...

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

Чтобы ответить на ваш первоначальный вопрос, этот график показывает, что:

MaybeT + State :: t -> (Maybe a, t) вычисление с учетом состояния, где может не быть значения, но всегда будет (возможно измененный) выход состояния
StateT + Maybe :: s -> Maybe (a, s) вычисление, в котором как состояние, так и значение могут отсутствовать

Ответ 3

Предположим, что вместо сохранения State/StateT для сохранения состояния ваших процедур вы использовали IORef в монаде IO.

Априори есть два способа, которыми вы могли бы хотеть mzero (или fail) вести себя в комбинации монадов IO и Maybe:

либо mzero уничтожает весь расчет, так что mzero <|> x = x; или
mzero заставляет текущее вычисление не возвращать значение, но сохраняются эффекты IO -type.

Похоже, вы хотите первый, так что состояние, заданное одной процедурой, "разворачивается" для следующей процедуры в цепочке <|> s.

Конечно, эту семантику невозможно реализовать. Мы не знаем, будет ли вычисление вызывать mzero до тех пор, пока мы его не запустим, но при этом могут иметь произвольные IO эффекты, такие как launchTheMissiles, которые мы не можем отменить.

Теперь попробуйте построить два разных стека трансформатора монады из Maybe и IO:

IOT Maybe - oops, этого не существует!
MaybeT IO

Тот, который существует (MaybeT IO), дает поведение mzero, которое возможно, а несуществующий IOT Maybe соответствует другому поведению.

К счастью, вы используете State ProcedureState, чьи эффекты можно отбросить, а не IO; вы хотите, чтобы блок монодарного трансформатора был StateT ProcedureState Maybe.

Ответ 4

Вы сможете ответить на вопрос самостоятельно, если попытаетесь написать "запустить" функции для обеих версий. У меня нет установленных трансформаторов MTL +, поэтому я не могу это сделать сам. Один из них вернет (может быть, состояние) другой Maybe (a, state).

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