Монада State

We use cookies. Read the Privacy and Cookie Policy

Модуль Control.Monad.State предоставляет тип newtype, который оборачивает вычисления с состоянием. Вот его определение:

newtype State s a = State { runState :: s –> (a, s) }

Тип State s a – это тип вычисления с состоянием, которое манипулирует состоянием типа s и имеет результат типа a.

Как и модуль Control.Monad.Writer, модуль Control.Monad.State не экспортирует свой конструктор значения. Если вы хотите взять вычисление с состоянием и обернуть его в newtype State, используйте функцию state, которая делает то же самое, что делал бы конструктор State.

Теперь, когда вы увидели, в чём заключается суть вычислений с состоянием и как их можно даже воспринимать в виде значений с контекстами, давайте рассмотрим их экземпляр класса Monad:

instance Monad (State s) where

   return x = State $ s –> (x, s)

   (State h) >>= f = State $ s –> let (a, newState) = h s

                                       (State g) = f a

                                   in g newState

Наша цель использования функции return состоит в том, чтобы взять значение и создать вычисление с состоянием, которое всегда содержит это значение в качестве своего результата. Поэтому мы просто создаём анонимную функцию s –> (x, s). Мы всегда представляем значение x в качестве результата вычисления с состоянием, а состояние остаётся неизменным, так как функция return должна помещать значение в минимальный контекст. Потому функция return создаст вычисление с состоянием, которое представляет определённое значение в качестве результата, а состояние сохраняет неизменным.

А что насчёт операции >>=? Ну что ж, результатом передачи вычисления с состоянием функции с помощью операции >>= должно быть вычисление с состоянием, верно? Поэтому мы начинаем с обёртки newtype State, а затем вызываем анонимную функцию. Эта анонимная функция будет нашим новым вычислением с состоянием. Но что же в ней происходит? Нам каким-то образом нужно извлечь значение результата из первого вычисления с состоянием. Поскольку прямо сейчас мы находимся в вычислении с состоянием, то можем передать вычислению с состоянием h наше текущее состояние s, что в результате даёт пару из результата и нового состояния: (a, newState).

До сих пор каждый раз, когда мы реализовывали операцию >>=, сразу же после извлечения результата из монадического значения мы применяли к нему функцию f, чтобы получить новое монадическое значение. В случае с монадой Writer после того, как это сделано и получено новое монадическое значение, нам по-прежнему нужно позаботиться о контексте, объединив прежнее и новое моноидные значения с помощью функции mappend. Здесь мы выполняем вызов выражения f a и получаем новое вычисление с состоянием g. Теперь, когда у нас есть новое вычисление с состоянием и новое состояние (известное под именем newState), мы просто применяем это вычисление с состоянием g к newState. Результатом является кортеж из окончательного результата и окончательного состояния!

Итак, при использовании операции >>= мы как бы «склеиваем» друг с другом два вычисления, обладающих состоянием. Второе вычисление скрыто внутри функции, которая принимает результат предыдущего вычисления. Поскольку функции pop и push уже являются вычислениями с состоянием, легко обернуть их в обёртку State:

import Control.Monad.State

pop :: State Stack Int

pop = state $ (x:xs) –> (x, xs)

push :: Int –> State Stack ()

push a = state $ xs –> ((), a:xs)

Обратите внимание, как мы задействовали функцию state, чтобы обернуть функцию в конструктор newtype State, не прибегая к использованию конструктора значения State напрямую.

Функция pop – уже вычисление с состоянием, а функция push принимает значение типа Int и возвращает вычисление с состоянием. Теперь мы можем переписать наш предыдущий пример проталкивания числа 3 в стек и выталкивания двух чисел подобным образом:

import Control.Monad.State

stackManip :: State Stack Int

stackManip = do

   push 3

   a <– pop

   pop

Видите, как мы «склеили» проталкивание и два выталкивания в одно вычисление с состоянием? Разворачивая его из обёртки newtype, мы получаем функцию, которой можем предоставить некое исходное состояние:

ghci> runState stackManip [5,8,2,1]

(5,[8,2,1])

Нам не требовалось привязывать второй вызов функции pop к образцу a, потому что мы вовсе не использовали этот образец. Значит, это можно было записать вот так:

stackManip :: State Stack Int

stackManip = do

   push 3

   pop

   pop

Очень круто! Но что если мы хотим сделать что-нибудь посложнее? Скажем, вытолкнуть из стека одно число, и если это число равно 5, просто протолкнуть его обратно в стек и остановиться. Но если число не равно 5, вместо этого протолкнуть обратно 3 и 8. Вот он код:

stackStuff :: State Stack ()

stackStuff = do

   a <– pop

   if a == 5

      then push 5

      else do

         push 3

         push 8

Довольно простое решение. Давайте выполним этот код с исходным стеком:

ghci> runState stackStuff [9,0,2,1,0] ((),[8,3,0,2,1,0])

Вспомните, что выражения do возвращают в результате монадические значения, и при использовании монады State одно выражение do является также функцией с состоянием. Поскольку функции stackManip и stackStuff являются обычными вычислениями с состоянием, мы можем «склеивать» их вместе, чтобы производить дальнейшие вычисления с состоянием:

moreStack :: State Stack ()

moreStack = do

   a <– stackManip

   if a == 100

      then stackStuff

      else return ()

Если результат функции stackManip при использовании текущего стека равен 100, мы вызываем функцию stackStuff; в противном случае ничего не делаем. Вызов return () просто сохраняет состояние как есть и ничего не делает.