Понимание StateMonad

Question

Я новичок в Haskell и пытаюсь понять это определение StateMonad, в частности, операцию связывания. Это взято из Обобщения Монад до Стрелок стр. 4.

instance Monad (StateMonad s) where
     return a = SM (\s -> (a, s))
     x >>= f = SM (\s -> let
                             SM x' = x
                             (a, s') = x' s
                             SM f' = f a
                             (b, s'') = f' s'
                         in (b, s''))

Answer 1

Для начала нужно понять тип >>=; Я предполагаю, что вы делаете, так как это на странице 2 этого документа, и вы прошли через это.

Определение для привязки может быть легче понять, если мы определим runState,

newtype SM s a = SM (s -> (a, s))

runState ::  SM a  -> s -> (a, s)
runState    (SM f)    s =  f s
-- this is equivalent to
-- runState (SM f) =  f

runState запускает монаду состояния путем извлечения функции f который преобразует состояние и применяет его в исходное состояние s, Функция f возвращает кортеж типа (a, s), Кортеж содержит значение (типа a), который зависит от состояния и нового состояния (типа s). Следующее эквивалентно

let (a, s') = runState x s
in ...

let SM x' = x
    (a, s') = x' s
in ...

Оба из них извлекают функцию x' за то, как государство трансформируется из xзатем примените его к исходному состоянию s, Полученный кортеж (a, s') содержит значение, зависящее от состояния aи новое государство s',

Мы можем заменить SM сопоставление с образцом в определении >>= с runState,

 x >>= f = SM (\s -> let
                         (a, s')  = runState x     s
                         (b, s'') = runState (f a) s'
                     in  (b, s''))

Теперь пройдемся по кусочкам.

Bind создает новый StateMonad с функцией, которая зависит от некоторого начального состояния s, Возвращает зависящее от состояния значение b и новое государство s'':

 x >>= f = SM (\s -> let
                         ...
                     in  (b, s''))

Государственно-зависимое значение a и новое государство s' рассчитываются путем запуска государственной монады x с начальным состоянием s:

                     let
                         (a, s')  = runState x     s

Новая государственная монада f a определяется из пользовательской функции f и зависящее от государства значение a, Эта вторая монада состояния запускается с промежуточным состоянием s', Это вычисляет другое зависящее от государства значение b и конечное состояние s'',

                         (b, s'') = runState (f a) s'   

Второе состояние зависит от значения b и конечное состояние s'' это то, что возвращается функцией, созданной для нового StateMonad,

Answer 2

Немного более короткий ответ в дополнение Cirdec"S...

Во-первых, напомним, что в x >>= f, x это государственная монада, f это FN, который возвращает монаду состояния, и x >>= f это также государственная монада.

Основная идея заключается в следующем. Учитывая некоторое текущее состояние s (это будет предоставлено позже, когда мы запустим государственную монаду, представленную x >>= f) мы сначала хотим запустить x с s, который даст некоторую ценность aвместе с новым государством s', Тогда мы хотим бежать f a, что дает нам еще одну государственную монаду. Мы не просто хотим запустить эту результирующую государственную монаду f a хотя с любым состоянием; скорее, мы хотим запустить его с состоянием, которое возникло в результате xа именно s', давая нам новое значение b и какое-то новое состояние s'', x >>= f будет представлять это вычисление из s -> (b, s''),

Помните: весь смысл использования монады состояний состоит в том, чтобы избежать явной передачи состояния вместе с другим параметром всем нашим функциям (это очень запутанно, очень быстро). Таким образом, идея заключается в том, чтобы государство должным образом проникало за кулисы, когда мы связываем действия с монадой государства.

Для этого мы (1) сопоставляем шаблон по x чтобы получить fn внутри, затем (2) запустите эту функцию с текущим состоянием s чтобы получить результат a и какое-то новое состояние s', Тогда мы (3) вычисляем f a, который возвращает монаду состояния и сопоставление с образцом этой монады, чтобы получить fn внутри; затем (4) запустить FN с состоянием s' чтобы получить значение b и какое-то окончательное состояние s'', (1) - (4) соответствуют четырем строкам, следующим сразу let в вашем коде. Что вы знаете, мы только что определили fn из s в (b, s''), который должным образом передает состояние за кулисами. Теперь мы просто завернем это в конструктор, и все готово. x >>= f Теперь представляет вычисление, которое мы можем запустить позже, предоставив начальное состояние.